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

long long Mod;
int pri[30],pw[30],gl[30],phi[30],tot,Phi;
int jc[30][1000010];
long long a[30],P[30];
long long qpow(long long a,long long p,int Mod)
{
	long long ret=1;
	for(;p;p>>=1,(a*=a)%=Mod)
		if(p&1) (ret*=a)%=Mod;
	return ret;
}
long long yzcnt(long long n,int p)
{
	long long ret=0;
	while(n) ret+=(n/=p);
	return ret;
}
long long S(long long n,int ind)
{
	if(n==0) return 1;
	return S(n/pri[ind],ind)*1ll*qpow(jc[ind][gl[ind]],n/gl[ind],gl[ind])%gl[ind]*jc[ind][n%gl[ind]]%gl[ind];
}
long long ExLucas(long long n,long long m)
{
	for(int i=1;i<=tot;i++)
	{
		a[i]=S(n,i)*qpow(S(m,i),phi[i]-1,gl[i])%gl[i]*qpow(S(n-m,i),phi[i]-1,gl[i])%gl[i];
//		printf("%lld %lld %lld %lld\n",S(n,i),S(m,i),S(n-m,i),a[i]);
		a[i]=a[i]*qpow(pri[i],yzcnt(n,pri[i])-yzcnt(m,pri[i])-yzcnt(n-m,pri[i]),gl[i])%gl[i];
		P[i]=gl[i];
//		printf("%lld %lld\n",a[i],P[i]);
	}
	long long ret=0;
	for(int i=1;i<=tot;i++)
		(ret+=a[i]*(Mod/P[i])*qpow(Mod/P[i],phi[i]-1,P[i]))%=Mod;
	return ret;
}
void init(int o, int p)
{
	Mod=p;
	for(int i=2;i*i<=p;i++)
	{
		if(p%i==0)
		{
			pri[++tot]=i;
			while(p%i==0)
				pw[tot]++,p/=i;
		}
	}
	if(p!=1) pri[++tot]=p,pw[tot]=1;
	Phi=1;
	for(int i=1;i<=tot;i++)
	{
		jc[i][0]=1;
		gl[i]=qpow(pri[i],pw[i],Mod+1);
		phi[i]=gl[i]-gl[i]/pri[i];
		Phi*=phi[i];
//		printf("(%d %d %d)\n",i,gl[i],phi[i]);
		for(int j=1;j<=gl[i];j++)
		{
			if(j%pri[i]) jc[i][j]=jc[i][j-1]*1ll*j%gl[i];
			else jc[i][j]=jc[i][j-1];
		}	
	}
	return;
}

int ask(long long n)
{
	long long ans=0;
	for(long long i=1;i<=n;i++)
		(ans+=i*ExLucas(2*n,n+i))%=Mod;
	ans*=qpow(qpow(2,2*n-1,Mod),Phi-1,Mod);
	return ans%Mod;
}