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

#define MAXLEN 32
#define SETSIZE 100000
#define MAXSTEPS (MAXLEN + 5)

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point points[MAXSTEPS];
    int count;
} VisitedSet;

typedef struct {
    VisitedSet visited;
    int x, y;
    int step;
    uint64_t count;
} State;

void visited_init(VisitedSet *vs) {
    vs->count = 0;
}

int visited_contains(VisitedSet *vs, int x, int y) {
    for (int i = 0; i < vs->count; i++) {
        if (vs->points[i].x == x && vs->points[i].y == y) return 1;
    }
    return 0;
}

void visited_add(VisitedSet *vs, int x, int y) {
    vs->points[vs->count].x = x;
    vs->points[vs->count].y = y;
    vs->count++;
}

void visited_remove(VisitedSet *vs) {
    vs->count--;
}

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char dir[] = {'E', 'W', 'S', 'N'};

uint64_t count_walks(int x, int y, int step, int target, VisitedSet *visited) {
    if (step == target) {
        return 1;
    }
    
    uint64_t total = 0;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (!visited_contains(visited, nx, ny)) {
            visited_add(visited, nx, ny);
            total += count_walks(nx, ny, step + 1, target, visited);
            visited_remove(visited);
        }
    }
    return total;
}

uint64_t count_from_prefix(const char *prefix, int target) {
    VisitedSet visited;
    visited_init(&visited);
    
    int x = 0, y = 0;
    visited_add(&visited, 0, 0);
    
    int step = 0;
    for (int i = 0; prefix[i] && step < 4; i++) {
        char c = prefix[i];
        for (int d = 0; d < 4; d++) {
            if (dir[d] == c) {
                x += dx[d];
                y += dy[d];
                break;
            }
        }
        visited_add(&visited, x, y);
        step++;
    }
    
    return count_walks(x, y, step, target, &visited);
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <length> [prefix]\n", argv[0]);
        fprintf(stderr, "  If prefix given, count walks starting with that prefix\n");
        fprintf(stderr, "  Otherwise, validate against known values and exit\n");
        return 1;
    }
    
    int target = atoi(argv[1]);
    
    if (argc >= 3) {
        uint64_t cnt = count_from_prefix(argv[2], target);
        printf("%llu\n", cnt);
        return 0;
    }
    
    uint64_t expected[] = {4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100};
    int lengths[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    printf("Validating implementation:\n");
    int ok = 1;
    for (int i = 0; i < 10; i++) {
        int len = lengths[i];
        uint64_t cnt = count_from_prefix("", len);
        printf("c(%d) = %llu (expected %llu) %s\n", len, cnt, expected[i], 
               cnt == expected[i] ? "OK" : "FAIL");
        if (cnt != expected[i]) ok = 0;
    }
    
    if (!ok) {
        fprintf(stderr, "Validation failed!\n");
        return 1;
    }
    printf("\nAll validations passed!\n");
    return 0;
}