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

typedef long long ll;

#define MAX_PATH 23

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point path[MAX_PATH];
    int path_len;
    int target_len;
} State;

// Direction: E=+x, N=+y, W=-x, S=-y
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int is_visited(State *s, int x, int y) {
    for (int i = 0; i < s->path_len; i++) {
        if (s->path[i].x == x && s->path[i].y == y) {
            return 1;
        }
    }
    return 0;
}

ll dfs(State *s, int x, int y, int len) {
    if (len == s->target_len) {
        return 1;
    }

    ll count = 0;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];

        if (!is_visited(s, nx, ny)) {
            s->path[s->path_len].x = nx;
            s->path[s->path_len].y = ny;
            s->path_len++;

            count += dfs(s, nx, ny, len + 1);

            s->path_len--;
        }
    }

    return count;
}

ll count_walks(const char *prefix, int target_len) {
    State s;
    memset(&s, 0, sizeof(s));
    s.target_len = target_len;

    // Start at origin
    s.path[0].x = 0;
    s.path[0].y = 0;
    s.path_len = 1;

    int x = 0, y = 0;

    // Apply prefix
    for (int i = 0; prefix[i]; i++) {
        int d = -1;
        if (prefix[i] == 'E') d = 0;
        else if (prefix[i] == 'N') d = 1;
        else if (prefix[i] == 'W') d = 2;
        else if (prefix[i] == 'S') d = 3;

        if (d >= 0) {
            x += dx[d];
            y += dy[d];
            s.path[s.path_len].x = x;
            s.path[s.path_len].y = y;
            s.path_len++;
        }
    }

    int prefix_len = strlen(prefix);

    // Count extensions
    return dfs(&s, x, y, prefix_len);
}

int main(int argc, char *argv[]) {
    // Validate against known values
    ll c1 = count_walks("", 1);
    ll c2 = count_walks("", 2);
    ll c3 = count_walks("", 3);
    ll c4 = count_walks("", 4);
    ll c10 = count_walks("", 10);

    printf("Validation:\n");
    printf("c(1) = %lld (expected 4) %s\n", c1, c1 == 4 ? "OK" : "FAIL");
    printf("c(2) = %lld (expected 12) %s\n", c2, c2 == 12 ? "OK" : "FAIL");
    printf("c(3) = %lld (expected 36) %s\n", c3, c3 == 36 ? "OK" : "FAIL");
    printf("c(4) = %lld (expected 100) %s\n", c4, c4 == 100 ? "OK" : "FAIL");
    printf("c(10) = %lld (expected 44100) %s\n", c10, c10 == 44100 ? "OK" : "FAIL");

    if (c1 == 4 && c2 == 12 && c3 == 36 && c4 == 100 && c10 == 44100) {
        printf("\nAll validation checks passed!\n");

        // Now count for the prefix given as argument
        if (argc > 1) {
            ll result = count_walks(argv[1], 22);
            printf("Walks with prefix \"%s\" to length 22: %lld\n", argv[1], result);
        }
    } else {
        printf("\nValidation FAILED - do not trust results\n");
        return 1;
    }

    return 0;
}