#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
ll inv2, inv4, P[kN][kN * 2], ans[kN], mod;
ll exgcd(int a, int b, ll &x, ll &y) {
  if (!b) { x = 1, y = 0; return a; }
  ll t = exgcd(b, a % b, y, x);
  y -= a / b * x;
}
ll qpow(ll a, ll b) { ll r = 1; while (b) { if (b & 1ll) r = r * a % mod; a = a * a % mod, b >>= 1ll; } return r; }
void preinit(ll pm) { mod = pm;
  P[0][0 + kN] = 1; inv2 = (mod + 1) / 2; ll y; exgcd(4, mod, inv4, y);
  inv4 = (inv4 + pm) % pm;
  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 + kN] % mod) % mod;
    }
  }
}
} // sub1

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

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

#define TEST
#ifdef TEST
ll o, T, p, n[N];
int main() {
#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);
#endif
  scanf("%lld%lld%lld", &o, &T, &p);
  init(o, p);
  for (int i = 1; i <= T; i++) { scanf("%lld", &n[i]); printf("%lld\n", ask(n[i])); }
  return 0;
}
#endif

answer.code: In function ‘int main()’:
answer.code:55:67: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int’ [-Wformat=]
   55 |   for (int i = 1; i <= T; i++) { scanf("%lld", &n[i]); printf("%lld\n", ask(n[i])); }
      |                                                                ~~~^     ~~~~~~~~~
      |                                                                   |        |
      |                                                                   |        int
      |                                                                   long long int
      |                                                                %d
answer.code: In function ‘long long int sub1::exgcd(int, int, long long int&, long long int&)’:
answer.code:18:5: warning: control reaches end of non-void function [-Wreturn-type]
   18 |   y -= a / b * x;
      |   ~~^~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |   scanf("%lld%lld%lld", &o, &T, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:55:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |   for (int i = 1; i <= T; i++) { scanf("%lld", &n[i]); printf("%lld\n", ask(n[i])); }
      |                                  ~~~~~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc1KMpqq.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccp4UlKp.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status