bee.cc

#include <iostream>
#include <cstring>
#define MOD 100000000000000LL;

using namespace std;

typedef long long ll;
const int MAXN = 100, L = 2 * MAXN + 1, ini = MAXN * L + MAXN;

ll M[L*L][MAXN+1];
ll DP(int pos, int mv) {
  ll &ans = M[pos][mv];
  if (ans >= 0)
    return ans;
  if (mv == 0)
    return ans = pos == ini;
  int d = (pos / L) & 1 ? 1 : -1;
  ans = (DP(pos+1, mv-1) + DP(pos-1, mv-1) +
    DP(pos-L, mv-1) + DP(pos-L+d, mv-1) +
    DP(pos+L, mv-1) + DP(pos+L+d, mv-1)) % MOD;
  return ans;
}

int main() {
  int n;
  cin >> n;
  memset(M, -1, sizeof M);
  cout << DP(ini, n) << endl;
}