#include "pilgrimage.h"
typedef long long ll;
int p[8],pk[8],rel[8],ps,P;
int bf[8][1000007],inv4;
void exgcd(int a,int b,int&x,int&y)
{
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b,y,x);y-=a/b*x;
}
int inv(int x,int p){int res;exgcd(x,p,res,x);return (res+p)%p;}
ll qpow(ll x,ll y,ll p){ll r=1;for(;y;x=x*x%p,y>>=1)if(y&1)r=r*x%p;return r;}
void init(int,int pr)
{
	inv4=inv(4,P=pr);
	for(int i=2;i*i<=P;++i) 
		if(!(pr%i))
	{
		p[++ps]=i;pk[ps]=1;
		while(!(pr%i))pr/=i,pk[ps]*=i;
	}
	if(pr!=1)p[++ps]=pr,pk[ps]=pr;
	for(int i=1;i<=ps;++i)
	{
		exgcd((P/pk[i])%pk[i],pk[i],rel[i],pr);
		if(rel[i]<0)rel[i]+=pk[i];
	}
	for(int i=1;i<=ps;++i)
	{
		bf[i][0]=1;
		for(int j=1;j<pk[i];++j)
			bf[i][j]=(ll)bf[i][j-1]*(j%p[i]?j:1)%pk[i];
	}
}
ll cf(int p,ll n){ll ans=0;while(n)ans+=(n/=p);return ans;}
int fl(int id,ll n)
{
	if(!n)return 1;
	return qpow(bf[id][pk[id]-1],n/p[id],pk[id])*bf[id][n%pk[id]]%pk[id];
}
int cal(int id,ll n,ll m)
{
	ll z=cf(p[id],n)-cf(p[id],n-m)-cf(p[id],m);int ans=1;while(z--&&ans)ans*=p[id];
	return ans?((ll)ans*fl(id,n)%pk[id]*inv(fl(id,m),pk[id])%pk[id]*inv(fl(id,n-m),pk[id])%pk[id]):0;
}
int C(ll n,ll m)
{
	int ans=0;
	for(int i=1;i<=ps;++i)
		ans=(ans+(ll)rel[i]*cal(i,n,m))%P;
	return ans;
}
int ask(ll n){return qpow(inv4,n,P)*n%P*C(n+n,n)%P;}