#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