#include<bits/stdc++.h>
#include"pilgrimage.h"
#define endl '\n'
#define int long long
using namespace std;
int mod,tot,inv4;
int a[7],b[7],PK[7];
int H[7][1000005],mp[1000005];
inline int power(int x,int k,int p){
int cur=1;x%=p;
while(k){
if(k&1)cur=cur*x%p;
x=x*x%p,k/=2;
}return cur;
}
int exgcd(int a,int b,int &x,int &y){
if(!b){x=1,y=0;return a;}
int res=exgcd(b,a%b,y,x);
y-=a/b*x; return res;
}
inline int getinv(int a,int p){
int x,y;exgcd(a,p,x,y);
return (x+p)%p;
}
int F(int n,int p,int pk){
if(!n) return 1;
return F(n/p,p,pk)*(((n/pk)&1)?pk-1:1)%pk*H[mp[p]][n%pk]%pk;
// return F(n/p,p,pk)*power(H[mp[p]][pk-1],n/pk,pk)%pk*H[mp[p]][n%pk]%pk;
}
int G(int n,int p){return n<p?0:G(n/p,p)+(n/p);}
inline int getlst(int n,int m,int p,int sum){
int fn=F(n,p,sum),fm=F(m,p,sum),fnm=F(n-m,p,sum);
int invm=getinv(fm,sum),invnm=getinv(fnm,sum);
int lst=power(p,G(n,p)-G(m,p)-G(n-m,p),sum);
return fn*invm%sum*invnm%sum*lst%sum;
}
inline int C(int n,int m,int p){
for(int i=0;i<tot;i++)b[i]=getlst(n,m,a[i],PK[i]);
int ans=0,sum=1;
for(int i=0;i<tot;i++)sum*=a[i];
for(int i=0;i<tot;i++){
int lst=sum/a[i],inv=getinv(lst,a[i]);
ans=(ans+b[i]*lst%mod*inv%mod)%mod;
}
return ans;
}
void init(int o,int p){
mod=p;int num=mod;
for(int i=2;i*i<=mod;i++){
if(num%i==0){
int pk=1;
while(num%i==0)pk*=i,num/=i;
H[tot][0]=1,mp[i]=tot;
for(int j=1;j<pk;j++)H[tot][j]=H[tot][j-1]*(j%i?j:1)%pk;
a[tot]=i,PK[tot]=pk,tot++;
}
}
if(num>1){
H[tot][0]=1,mp[num]=tot;
for(int i=1;i<num;i++)H[tot][i]=H[tot][i-1]*(i%num?i:1)%num;
a[tot]=PK[tot]=num,tot++;
}
inv4=getinv(4,mod);
}
int ask(int n){
return n%mod*power(inv4,n,mod)%mod*C(n*2,n,mod)%mod;
}
// signed main(){
// // freopen("test.in","r",stdin);
// // freopen("test.out","w",stdout);
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// int T;cin>>T>>T>>mod,init(0,mod);
// while(T--){
// int n;cin>>n;
// cout<<ask(n)<<endl;
// }
// return 0;
// }