#include "pilgrimage.h"
#include <bits/stdc++.h>
using namespace std;

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define ll long long

// TODO: your functions

ll ksm(ll x, ll y, ll Mod) {
	ll sum = 1;
	for(; y; y >>= 1, x = x * x % Mod)
		if(y & 1) sum = sum * x % Mod;
	return sum;
}

ll mo, i2;

int p[20], c[20], pc[20], m = 0;
int qz[10][1000005], qu[10];

void init(int o, int ip) {
	mo = ip;
	i2 = (mo + 1) / 2;
	for(int i = 2, j = mo; i <= j; ++i) {
		if(j % i != 0) continue;
		p[++m] = i, pc[m] = 1, c[m] = 0;
		while(j % i == 0) {
			pc[m] *= i, ++c[m];
			j /= i;
		}
	}
	fo(i, 1, m) {
		qz[i][0] = 1;
		fo(j, 1, pc[i]) {
			qz[i][j] = qz[i][j - 1];
			if(j % p[i] != 0)
				(qz[i][j] *= j) %= mo;
		}
		qu[i] = qz[i][pc[i]];
	}
	return;
}

int Re[20];

ll exlucas(ll x, int id) {
	if(x == 0) return 1;
	ll res = qu[id] * exlucas(x / p[id], id) % pc[id];
	res = ksm(res, x / pc[id], pc[id]);
	res = res * qz[id][x % pc[id]] % mo;
	return res;
}

void exgcd(ll a, ll b, ll &x, ll &y) {
	if(!b) {
		x = 1, y = 0; return;
	}
	ll nx, ny;
	exgcd(b, a % b, nx, ny);
	x = ny, y = nx - a / b * ny;
	return;
}

void Merge(int &x, int &y, int nx, int ny) {
	ll k1, k2;
	int nny = y * ny;
	exgcd(y, ny, k1, k2);
//	printf("%d %d\n", k1, k2);
	k1 = (k1 * (nx - x) % nny + nny) % nny;
	x = (k1 * y + x) % nny;
	y = nny;
	return;
}

int ask(ll n) {
	fo(i, 1, m) {
		int stp = 0;
		for(ll x = 2 * n; x; x /= p[i])
			stp += x / p[i];
		for(ll x = n; x; x /= p[i])
			stp -= 2 * (x / p[i]);
		if(stp >= c[i]) {Re[i] = 0; continue;}
		ll z1 = exlucas(2 * n, i), z2 = exlucas(n, i);
		z2 = z2 * z2 % pc[i];
		z2 = ksm(z2, pc[i] / p[i] * (p[i] - 1) - 1, pc[i]);
//		printf("%lld %lld %lld\n", z1, z2, ksm(p[i], stp, pc[i]));
		Re[i] = z1 * z2 % pc[i] * ksm(p[i], stp, pc[i]) % pc[i];
//		printf("%lld\n", Re[i]);
	}
	int u, o;
	u = 0, o = 1;
	fo(i, 1, m) {
		Merge(u, o, Re[i], pc[i]);
	}
//	printf("%d %d\n", u, o);
	u = u * (n % mo) % mo * ksm(i2, 2 * n, mo) % mo;
	return u;
}