#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define MAX_LEN 22
#define GRID_SIZE 100
#define OFFSET 50  // Offset to handle negative coordinates

typedef struct {
    uint8_t visited[GRID_SIZE][GRID_SIZE];
} State;

static long count_walks;

void dfs(State *state, int x, int y, int steps_left, int target_len, const char *prefix, int prefix_len) {
    if (steps_left == 0) {
        count_walks++;
        return;
    }
    
    // Try all 4 directions: E, N, W, S
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        // Check bounds (with padding)
        if (nx < 0 || nx >= GRID_SIZE || ny < 0 || ny >= GRID_SIZE) continue;
        
        // Check if not visited
        if (state->visited[nx][ny]) continue;
        
        // Mark as visited
        state->visited[nx][ny] = 1;
        
        // Recurse
        dfs(state, nx, ny, steps_left - 1, target_len, prefix, prefix_len);
        
        // Unmark (backtrack)
        state->visited[nx][ny] = 0;
    }
}

long count_extended(const char *prefix) {
    int prefix_len = strlen(prefix);
    
    State state;
    memset(&state.visited, 0, sizeof(state.visited));
    
    // Start at origin with offset
    int x = OFFSET;
    int y = OFFSET;
    state.visited[x][y] = 1;
    
    // Apply prefix steps
    for (int i = 0; i < prefix_len; i++) {
        char c = prefix[i];
        if (c == 'E') x++;
        else if (c == 'W') x--;
        else if (c == 'N') y++;
        else if (c == 'S') y--;
        
        if (x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE) {
            printf("ERROR: prefix takes us out of bounds\n");
            return -1;
        }
        state.visited[x][y] = 1;
    }
    
    // Count extensions
    count_walks = 0;
    int remaining = MAX_LEN - prefix_len;
    dfs(&state, x, y, remaining, MAX_LEN, prefix, prefix_len);
    
    return count_walks;
}

int main(int argc, char *argv[]) {
    const char *prefix = "";
    if (argc > 1) {
        prefix = argv[1];
    }
    
    long result = count_extended(prefix);
    printf("%ld\n", result);
    return 0;
}