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

#define GRID_SIZE 100
#define OFFSET 50

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) {
    if (steps_left == 0) {
        count_walks++;
        return;
    }
    
    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];
        
        if (nx < 0 || nx >= GRID_SIZE || ny < 0 || ny >= GRID_SIZE) continue;
        if (state->visited[nx][ny]) continue;
        
        state->visited[nx][ny] = 1;
        dfs(state, nx, ny, steps_left - 1);
        state->visited[nx][ny] = 0;
    }
}

long count_walks_of_length(int target_len, const char *prefix) {
    int prefix_len = strlen(prefix);
    
    State state;
    memset(&state.visited, 0, sizeof(state.visited));
    
    int x = OFFSET;
    int y = OFFSET;
    state.visited[x][y] = 1;
    
    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) {
            return -1;
        }
        state.visited[x][y] = 1;
    }
    
    count_walks = 0;
    int remaining = target_len - prefix_len;
    dfs(&state, x, y, remaining);
    
    return count_walks;
}

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