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

// Use a simple visited set with coordinate offset to handle negative coords
// Assuming walks don't go more than ±50 in any direction for length 22
#define OFFSET 100
#define SIZE 200

// 3D array: visited[x+OFFSET][y+OFFSET] = 1 if visited
char visited[SIZE][SIZE];

// Directions: E, N, W, S
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

long long count_walks(int x, int y, int remaining) {
    if (remaining == 0) {
        return 1;
    }
    
    long long count = 0;
    
    // Try all 4 directions
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        // Check bounds and if not visited
        if (nx + OFFSET >= 0 && nx + OFFSET < SIZE && 
            ny + OFFSET >= 0 && ny + OFFSET < SIZE && 
            !visited[nx + OFFSET][ny + OFFSET]) {
            
            visited[nx + OFFSET][ny + OFFSET] = 1;
            count += count_walks(nx, ny, remaining - 1);
            visited[nx + OFFSET][ny + OFFSET] = 0;
        }
    }
    
    return count;
}

long long count_with_prefix(const char *prefix_str, int total_length) {
    memset(visited, 0, sizeof(visited));
    
    int x = 0, y = 0;
    visited[x + OFFSET][y + OFFSET] = 1;
    
    // Apply prefix
    for (int i = 0; prefix_str[i]; i++) {
        char c = prefix_str[i];
        if (c == 'E') x++;
        else if (c == 'W') x--;
        else if (c == 'N') y++;
        else if (c == 'S') y--;
        
        visited[x + OFFSET][y + OFFSET] = 1;
    }
    
    int prefix_len = strlen(prefix_str);
    int remaining = total_length - prefix_len;
    
    return count_walks(x, y, remaining);
}

int main() {
    // Validate against known values
    printf("Validation:\n");
    printf("c(1) = %lld (expected 4)\n", count_with_prefix("", 1));
    printf("c(2) = %lld (expected 12)\n", count_with_prefix("", 2));
    printf("c(3) = %lld (expected 36)\n", count_with_prefix("", 3));
    printf("c(4) = %lld (expected 100)\n", count_with_prefix("", 4));
    printf("c(10) = %lld (expected 44100)\n", count_with_prefix("", 10));
    
    printf("\nComputing EESS prefix:\n");
    long long result = count_with_prefix("EESS", 22);
    printf("count=%lld\n", result);
    
    return 0;
}