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

/* Self-avoiding walk counter for square lattice Z^2
 * Counts paths of a given length starting with an optional prefix
 */

#define MAX_STEPS 22
#define GRID_SIZE 128  /* 2^7, enough for 22-step walks with some margin */
#define GRID_OFFSET 64

typedef struct {
    unsigned char visited[GRID_SIZE][GRID_SIZE];
} Grid;

long long count_walks(const char *prefix, int target_length);

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

char *dir_chars = "ENWS";

long long dfs(Grid *grid, int x, int y, int steps_remaining, int target_length) {
    if (steps_remaining == 0) {
        return 1;
    }
    
    long long count = 0;
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        /* Check bounds (with offset) */
        if (nx < 0 || nx >= GRID_SIZE || ny < 0 || ny >= GRID_SIZE) {
            continue;
        }
        
        /* Check if already visited */
        if (grid->visited[nx][ny]) {
            continue;
        }
        
        /* Mark as visited and recurse */
        grid->visited[nx][ny] = 1;
        count += dfs(grid, nx, ny, steps_remaining - 1, target_length);
        grid->visited[nx][ny] = 0;
    }
    
    return count;
}

long long count_walks(const char *prefix, int target_length) {
    Grid grid;
    memset(&grid.visited, 0, sizeof(grid.visited));
    
    int x = GRID_OFFSET;
    int y = GRID_OFFSET;
    grid.visited[x][y] = 1;  /* Mark origin as visited */
    
    int steps_taken = 0;
    
    /* Process prefix */
    for (int i = 0; prefix[i] != '\0'; i++) {
        char c = prefix[i];
        int dir = -1;
        
        if (c == 'E') dir = 0;
        else if (c == 'N') dir = 1;
        else if (c == 'W') dir = 2;
        else if (c == 'S') dir = 3;
        else {
            fprintf(stderr, "Invalid direction: %c\n", c);
            return -1;
        }
        
        x += dx[dir];
        y += dy[dir];
        
        if (x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE) {
            fprintf(stderr, "Prefix goes out of bounds\n");
            return -1;
        }
        
        if (grid.visited[x][y]) {
            fprintf(stderr, "Prefix self-intersects\n");
            return -1;
        }
        
        grid.visited[x][y] = 1;
        steps_taken++;
    }
    
    int remaining = target_length - steps_taken;
    if (remaining < 0) {
        fprintf(stderr, "Prefix longer than target length\n");
        return -1;
    }
    
    return dfs(&grid, x, y, remaining, target_length);
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <target_length> [prefix]\n", argv[0]);
        fprintf(stderr, "Example: %s 10\n", argv[0]);
        fprintf(stderr, "Example: %s 22 ESSS\n", argv[0]);
        return 1;
    }
    
    int target_length = atoi(argv[1]);
    const char *prefix = (argc > 2) ? argv[2] : "";
    
    if (target_length < 0 || target_length > MAX_STEPS) {
        fprintf(stderr, "Target length must be between 0 and %d\n", MAX_STEPS);
        return 1;
    }
    
    long long result = count_walks(prefix, target_length);
    printf("%lld\n", result);
    
    return 0;
}