#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _1 first
#define _2 second
const int N = 1000010;
int p;
vector <pair <int, int> > vec;
vector <vector <int> > fac;
int exgcd(int a, int b, int & x, int & y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int inv(int a, int b) {
	int x, y, d = exgcd(a, b, x, y);
	int t = b / d;
	x = (x % t + t) % t;
	return x;
}
int quick_pow(int x, ll y, int p) {
	int res = 1;
	for (; y; y >>= 1, x = (ll) x * x % p)
		if (y & 1) res = (ll) res * x % p;
	return res;
}
int calc(ll n, int k) {
	int x = vec[k]._1;
	int p = vec[k]._2;
	return n ? (ll) quick_pow(fac[k][p], n / p, p) * fac[k][n % p] % p * calc(n / x, k) % p : 1;
}
int solve(ll n, ll m, int k) {
	int cnt = 0;
	int x = vec[k]._1;
	int p = vec[k]._2;
	for (ll i = n; i; i /= x) cnt += i / x;
	for (ll i = m; i; i /= x) cnt -= i / x;
	for (ll i = n - m; i; i /= x) cnt -= i / x;
	return (ll) quick_pow(x, cnt, p) * calc(n, k) % p * inv(calc(m, k), p) % p * inv(calc(n - m, k), p) % p;
}
void init(int p) {
	for (int i = 2; i * i <= p; ++i) {
		if (p % i) continue;
		int d = 1;
		while (!(p % i)) {
			p /= i;
			d *= i;
		}
		vec.emplace_back(i, d);
	}
	if (p > 1)
		vec.emplace_back(p, p);
	for (size_t i = 0; i < vec.size(); ++i) {
		static vector <int> t;
		t.resize(vec[i]._2 + 1);
		t[0] = 1;
		for (int j = 1; j <= vec[i]._2; ++j)
			t[j] = (ll) t[j - 1] * (j % vec[i]._1 ? j : 1) % vec[i]._2;
		fac.emplace_back(t);
	}
}
int Lucas(ll n, ll m) {
	int res = 0;
	for (size_t i = 0; i < vec.size(); ++i) {
		int t = solve(n, m, i);
		res = (res + (ll) t * (p / vec[i]._2) % p * inv(p / vec[i]._2 % vec[i]._2, vec[i]._2) % p) % p;
	}
	return res;
}
int opt, T;
int main() {
	scanf("%d%d%d", &opt, &T, &p);
	init(p);
	while (T--) {
		ll n;
		scanf("%lld", &n);
		printf("%lld\n", (ll) inv(quick_pow(4, n, p), p) * (n % p) % p * Lucas(2 * n, n) % p);
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:77:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |         scanf("%d%d%d", &opt, &T, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
answer.code:81:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |                 scanf("%lld", &n);
      |                 ~~~~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/cctdht7n.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccGXdUqo.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccGXdUqo.o: in function `main':
implementer.cpp:(.text.startup+0x2b): undefined reference to `init(int, int)'
/usr/bin/ld: implementer.cpp:(.text.startup+0x16c): undefined reference to `ask(long long)'
collect2: error: ld returned 1 exit status