#include<bits/stdc++.h>
#include"pilgrimage.h"
using namespace std;
using ll=long long;
ll ksm(ll a,ll b,ll mod)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
class exLucas
{
	int pr[20],cnt[20],tot;
	ll P;
	ll val[20];
	ll rem[20];
	ll pval[20];
	vector<ll> prod[20];
	void exgcd(ll x,ll y,ll &a,ll &b)
	{
		if(!y)
		{
			a=1;
			b=0;
			return ;
		}
		exgcd(y,x%y,b,a);
		b-=a*(x/y);
	}
	ll inverse(ll x,ll m)
	{
		ll a,b;
		exgcd(x,m,a,b);
		return (a%m+m)%m;
	}
	void initCrt()
	{
		for(int i=0;i<tot;i++)
			val[i]=P/pval[i]*inverse(P/pval[i],pval[i]);
	}
	ll crt()
	{
		ll ans=0;
		for(int i=0;i<tot;i++)
			ans=(ans+rem[i]*val[i])%P;
		return ans;
	}
	ll cntp(ll n,ll p)
	{
		if(!n) return 0;
		return n/p+cntp(n/p,p);
	}
	ll calc(ll x,ll pr,ll pval,int ind)
	{
		if(!x) return 1;
		ll s=((x/pval)&1)?(pval-1):1;
		s=s*prod[ind][x%pval];
		return s*calc(x/pr,pr,pval,ind)%pval;
	}
	public:
		void init(int p)
		{
			P=p;
			tot=0;
			for(int i=2;i*i<=p;i++)
				if(p%i==0)
				{
					pr[tot]=i;
					pval[tot]=1;
					while(p%i==0)
					{
						p/=i;
						pval[tot]*=i;
						cnt[tot]++;
					}
					tot++;
				}
			if(p>1)
			{
				pr[tot]=p;
				pval[tot]=p;
				cnt[tot++]=1;
			}
			for(int i=0;i<tot;i++)
			{
				prod[i]={1};
				for(int j=1;j<pval[i];j++)
					if(j%pr[i]==0)
						prod[i].push_back(prod[i].back());
					else
						prod[i].push_back(prod[i].back()*j%pval[i]);
			}
			initCrt();
		}
		exLucas(){}
		exLucas(int p){init(p);}
		ll calc(ll n,ll m)
		{
			for(int i=0;i<tot;i++)
			{
				ll cp=cntp(n,pr[i])-cntp(m,pr[i])-cntp(n-m,pr[i]);
				rem[i]=calc(n,pr[i],pval[i],i)%pval[i]*inverse(calc(m,pr[i],pval[i],i),pval[i])*inverse(calc(n-m,pr[i],pval[i],i),pval[i])%pval[i];
			}
			return crt();
		}
};
exLucas exLucasCalculator;
ll p;
void init(int o,int p)
{
	::p=p;
	exLucasCalculator.init(p);
}
int ask(ll n)
{
	ll inv=ksm((p+1)/2,n+n,p);
	return inv*(n%p)*exLucasCalculator.calc(n+n,n)%p;
}