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

#define MAX_LENGTH 22
#define MAX_CELLS 1000

typedef struct {
    int x, y;
} Cell;

typedef struct {
    Cell visited[MAX_CELLS];
    int count;
    int x, y;
} State;

long long count_walks;

void dfs(State *state, int target_length, int current_length) {
    if (current_length == target_length) {
        count_walks++;
        return;
    }

    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    
    for (int dir = 0; dir < 4; dir++) {
        int nx = state->x + dx[dir];
        int ny = state->y + dy[dir];
        
        int visited = 0;
        for (int i = 0; i < state->count; i++) {
            if (state->visited[i].x == nx && state->visited[i].y == ny) {
                visited = 1;
                break;
            }
        }
        
        if (!visited && state->count < MAX_CELLS) {
            state->visited[state->count].x = nx;
            state->visited[state->count].y = ny;
            state->count++;
            
            int old_x = state->x;
            int old_y = state->y;
            state->x = nx;
            state->y = ny;
            
            dfs(state, target_length, current_length + 1);
            
            state->x = old_x;
            state->y = old_y;
            state->count--;
        }
    }
}

long long count_extensions(char *prefix, int target_length) {
    State state;
    state.x = 0;
    state.y = 0;
    state.count = 1;
    state.visited[0].x = 0;
    state.visited[0].y = 0;
    
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    char dirs[] = "ENWS";
    
    for (int i = 0; i < strlen(prefix); i++) {
        char c = prefix[i];
        int dir_idx = -1;
        for (int j = 0; j < 4; j++) {
            if (dirs[j] == c) {
                dir_idx = j;
                break;
            }
        }
        
        if (dir_idx == -1) {
            fprintf(stderr, "Invalid direction: %c\n", c);
            return -1;
        }
        
        int nx = state.x + dx[dir_idx];
        int ny = state.y + dy[dir_idx];
        
        int visited = 0;
        for (int j = 0; j < state.count; j++) {
            if (state.visited[j].x == nx && state.visited[j].y == ny) {
                visited = 1;
                break;
            }
        }
        
        if (visited) {
            fprintf(stderr, "Prefix creates a collision at (%d, %d)\n", nx, ny);
            return -1;
        }
        
        state.visited[state.count].x = nx;
        state.visited[state.count].y = ny;
        state.count++;
        state.x = nx;
        state.y = ny;
    }
    
    count_walks = 0;
    dfs(&state, target_length, strlen(prefix));
    return count_walks;
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <prefix> [target_length]\n", argv[0]);
        fprintf(stderr, "Example: %s \"E\" 22\n", argv[0]);
        return 1;
    }
    
    char *prefix = argv[1];
    int target_length = 22;
    if (argc >= 3) {
        target_length = atoi(argv[2]);
    }
    
    long long result = count_extensions(prefix, target_length);
    printf("%lld\n", result);
    
    return 0;
}