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

#define GRID_SIZE 150
#define OFFSET 75  // center at 75,75

// Track visited cells - index by coord+OFFSET
int visited[GRID_SIZE][GRID_SIZE];

long long count_walks(int steps_left, int x, int y) {
    if (steps_left == 0) {
        return 1;
    }
    
    long long count = 0;
    // Try each direction: 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];
        int gx = nx + OFFSET;
        int gy = ny + OFFSET;
        
        // Check bounds and not visited
        if (gx >= 0 && gx < GRID_SIZE && gy >= 0 && gy < GRID_SIZE && !visited[gx][gy]) {
            visited[gx][gy] = 1;
            count += count_walks(steps_left - 1, nx, ny);
            visited[gx][gy] = 0;
        }
    }
    
    return count;
}

long long count_saw(const char* prefix, int total_length) {
    // Initialize visited array
    memset(visited, 0, sizeof(visited));
    
    // Start at origin
    int x = 0, y = 0;
    int gx = x + OFFSET;
    int gy = y + OFFSET;
    visited[gx][gy] = 1;
    
    // Process prefix steps
    int prefix_len = strlen(prefix);
    for (int i = 0; i < prefix_len; i++) {
        if (prefix[i] == 'E') x++;
        else if (prefix[i] == 'W') x--;
        else if (prefix[i] == 'N') y++;
        else if (prefix[i] == 'S') y--;
        
        gx = x + OFFSET;
        gy = y + OFFSET;
        visited[gx][gy] = 1;
    }
    
    // Count remaining walks
    int remaining = total_length - prefix_len;
    return count_walks(remaining, x, y);
}

int main(int argc, char** argv) {
    // Test cases
    printf("Testing known values:\n");
    printf("c(1)=4, got %lld\n", count_saw("", 1));
    printf("c(2)=12, got %lld\n", count_saw("", 2));
    printf("c(3)=36, got %lld\n", count_saw("", 3));
    printf("c(4)=100, got %lld\n", count_saw("", 4));
    printf("c(10)=44100, got %lld\n", count_saw("", 10));
    
    // Read prefix from command line
    if (argc > 1) {
        const char* prefix = argv[1];
        int total_length = 22;
        if (argc > 2) {
            total_length = atoi(argv[2]);
        }
        long long count = count_saw(prefix, total_length);
        printf("Count for prefix '%s' at length %d: %lld\n", prefix, total_length, count);
    }
    
    return 0;
}