#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
typedef long long ll;
int mo;
ll n,m;
ll p_cnt[25],p_num[25];
int cnt=0;
int phi[25][N],ni[25][N];
void exgcd(int a,int b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
ll mi(ll x,ll y,ll p)
{
	ll res=1;
//	x%=p,y%=p; 
	for(;y;y>>=1,x=1ll*x*x%p)
		if(y&1) res=1ll*res*x%p;
	return res;
}
void div_p(int p)
{
	int i,j;
	ll x,y;
	for(i=2;i<=p;i++)
	{
		if(p%i) continue;
		p_num[++cnt]=i,p_cnt[cnt]=1;
		while(p%i==0) p/=i,p_cnt[cnt]*=i;
		phi[cnt][0]=1;
		ni[cnt][0]=1; 
	//	cout<<"yin "<<i<<endl;
		for(j=1;j<=p_cnt[cnt];j++) 
		{
	//		cout<<j<<" ";
			if(j%p_num[cnt]==0)
			{
				phi[cnt][j]=phi[cnt][j-1];
				ni[cnt][j]=-1;
			}
			else 
			{
	//			cout<<phi[cnt][j-1]*j<<endl;
				phi[cnt][j]=1ll*phi[cnt][j-1]*j%p_cnt[cnt];
				exgcd(j,p_cnt[cnt],x,y);
				if(x<0) x+=p_cnt[cnt];
				ni[cnt][j]=x;
			}
		//	cout<<"yiny "<<j<<" "<<ni[cnt][j]<<endl;
		}
		if(p==1)
		{
			cout<<"";
			return;
		}
	}
	cout<<"";
}
ll f(int lei,ll v)
{
	if(v<=p_num[lei]) return phi[lei][v];
//	cout<<lei<<" "<<v<<" "<<cal_ji(lei,v)<<endl; 
	return 1ll*((v/p_cnt[lei])&1?p_cnt[lei]-phi[lei][v%p_cnt[lei]]:phi[lei][v%p_cnt[lei]])*f(lei,v/p_num[lei])%p_cnt[lei];
}
//ll xi[N];
int calc(ll x,ll y)
{
	ll i,j,a,b,t,ans=0;
//	cout<<x<<" "<<y<<endl;
	for(i=1;i<=cnt;i++)
	{
		a=f(i,x)*ni[i][f(i,y)]*ni[i][f(i,x-y)]%p_cnt[i];
		for(j=x;j;j/=mo) t+=j/mo;
		for(j=y;j;j/=mo) t-=j/mo;
		for(j=x-y;j;j/=mo) t-=j/mo;
	//	t=get_vp(i,x)-get_vp(i,y)-get_vp(i,x-y);
		b=mi(p_num[i],t,p_cnt[i]);
		ans=(ans+1ll*a*b%p_cnt[i]*(mo/p_cnt[i])%mo*ni[i][mo/p_cnt[i]]%mo)%mo;
	}
//	ll xx,yy,ans=0,tm;
//	for(i=1;i<=cnt;i++)
//	{
//		tm=mo/p_cnt[i];
//		exgcd(tm,p_cnt[i],xx,yy);
//		if(xx<0) xx+=p_cnt[i];
//		ans=(ans+xi[i]*tm*xx%mo);
//	} 
	return ans%mo;
}
int er[N],er_ni[N],mod;
void init (int o, int p)
{
	mo=p;
	div_p(p);
	int i,j;
	er[0]=er_ni[0]=1;
	er_ni[1]=(mo+1)/2;
	for(i=1;i<=N-5;i++)
	{
		er[i]=er[i-1]*2%mo;
		er_ni[i]=1ll*er_ni[i-1]*er_ni[1]%mo;
		if(er[i]==1) mod=i;
	}
}
int ask (long long n)
{
	return 1ll*calc(2*n,n)*er_ni[2*n%mod]%mo*(n%mo)%mo;
}