#include <bits/stdc++.h>
#define N 200005
#define ll long long
#define DEBUG
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
// TODO: your functions

namespace sub1 {
#define kN 3005
int inv2, inv4, P[kN][kN * 2], ans[kN];
int qpow(int a, int b, int mod) { int r = 1; while (b) { if (b & 1) r = 1ll * r * a % mod; a = 1ll * a * a % mod, b >>= 1; } return r; }
void preinit(int mod) {
  P[0][0 + kN] = 1; inv2 = qpow(2, mod - 2, mod), inv4 = qpow(4, mod - 2, mod);
  for (int k = 1; k <= 3000; k++) {
    for (int i = -3000; i <= 3000; i++) {
      P[k][i + kN] = 1ll * (1ll * P[k - 1][i - 1 + kN] * inv4 % mod + 1ll * P[k - 1][i + kN] * inv2 % mod + 1ll * P[k - 1][i + 1 + kN] * inv4 % mod) % mod;
    }
    for (int i = -3000; i <= 3000; i++) {
      ans[k] = (ans[k] + 1ll * abs(i) * P[k][i] % mod) % mod;
    }
  }
}
} // sub1

void init(int o, int p) { // o is subtask id, p is mod
	// TODO: your init
  sub1::preinit(p);
}

int ask(long long n) {
	// TODO: your ask
  if (n <= 3000) { return sub1::ans[n]; }
	return 1;
}