#include <bits/stdc++.h>
#include "pilgrimage.h"

using namespace std;

int fac[15][1000005];
int pr[15], pw[15], prw[15], K[15], c = 0, phi;
int b[15];
int mod;
long long IV, VI;
int MOD(long long x)
{
	x -= ((__int128(IV) * x) >> 50) * mod;
	return (x < mod) ? x : (x - mod);
}
int PHI(long long x)
{
	x -= ((__int128(VI) * x) >> 50) * phi;
	return (x < phi) ? x : (x - phi);
}
int qpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1)
			ans = MOD((long long)ans * x);
		x = MOD((long long)x * x);
		y >>= 1;
	}
	return ans;
}
void getp(int x)
{
	int i;
	phi = x;
	for(i = 2; (long long)i * i <= x; i++)
		if(!(x % i))
		{
			pr[++c] = i;
			prw[c] = 1;
			while(!(x % i))
			{
				++pw[c];
				prw[c] *= i;
				x /= i;
			}
			phi = phi / i * (i - 1);
//			printf("!%d %d\n", pr[c], pw[c]);
		}
	if(x != 1)
	{
		pr[++c] = x;
		pw[c] = 1;
		prw[c] = x;
		phi = phi / x * (x - 1);
	}
}
void init(int o, int p)
{
	int i, j, ph;
	mod = p;
	getp(p);
	IV = (1LL << 50) / mod;
	VI = (1LL << 50) / phi;
	for(i = 1; i <= c; i++)
	{
		ph = (long long)phi * pr[i] / prw[i] / (pr[i] - 1);
		K[i] = MOD(MOD((long long)qpow(mod - prw[i], ph - 1) * prw[i]) + 1);
		fac[i][0] = 1;
		for(j = 1; j <= prw[i]; j++)
			if(j % pr[i])
				fac[i][j] = MOD((long long)fac[i][j - 1] * j);
			else
				fac[i][j] = fac[i][j - 1];
//		printf("!%d\n", K[i]);
	}
}
pair< int, pair<int, int> > getf(long long x, int m)
{
	pair< int, pair<int, int> > o = make_pair(1, make_pair(0, 0));
	while(x >= pr[m])
	{
		o = make_pair(MOD((long long)fac[m][x % prw[m]] * o.first), make_pair(PHI(x / pr[m] + o.second.first), PHI(x / prw[m] + o.second.second)));
		x /= pr[m];
		if(!o.first)
			break;
	}
	return make_pair(MOD((long long)o.first * fac[m][x]), make_pair(o.second.first, o.second.second));
}
int C(long long x, int m)
{
	pair< int, pair<int, int> > o2 = getf(x << 1, m), o = getf(x, m);
	if(!o2.first)
		return 0;
	int fv = MOD((long long)o2.first * qpow(o.first, phi - 2)), po = PHI(o2.second.first + phi - PHI(o.second.first << 1));
	int po2 = PHI(o2.second.second + phi - PHI(o.second.second << 1));
//	printf("???%d %d\n", po, po2);
	fv = MOD(MOD((long long)fv * qpow(pr[m], po)) * qpow(fac[m][prw[m]], po2));
//	printf("!%d %d\n", pr[m], fv);
	return fv;
}
int ask(long long n)
{
	int i, res, sum = 0;
	n--;
	res = MOD((long long)qpow((mod + 1) / 2, PHI(2 * n + 1)) * MOD(2 * n + 1));
	for(i = 1; i <= c; i++)
		sum = MOD(sum + MOD((long long)K[i] * C(n, i)));
	return MOD((long long)sum * res);
}