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

using namespace std;
using E=long long;

E mod;
vector<pair<int,int>> divsp;
vector<int> val;

E ksm(E a,E b,E MOD){
  //cerr<<"b="<<b<<endl;
  E ret=1;
  a%=MOD;
  while(b){
    if(b&1) ret=ret*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return ret;
}

E exgcd(E a,E b,E &x,E &y){
  if(!b){
    return x=1,y=0,a;
  }
  E d=exgcd(b,a%b,y,x);
  return y-=a/b*x,d;
}

E inverse(E a,E mod){
  assert(__gcd(a,mod)==1);
  a%=mod;
  assert(a!=0);
  E X=0,Y=0;
  E d=exgcd(a,mod,X,Y);
  return (X%mod+mod)%mod;
}

E calcu(E n,E p,E q,E pq){
  if(n==0) return 1;
  E ret=1;
  for(int i=1; i<=(n%pq); i++){
    if(i%p) ret=ret*i%pq;
  }
  E x=1;
  for(int i=1; i<pq; i++){
    if(i%p) x=x*i%pq;
  }
  ret=ret*ksm(x,n/pq,pq)%pq;
  ret=ret*calcu(n/p,p,q,pq)%pq;
  return ret;
}

E C(E n,E m,E p,E q){
  E x=0,y=0,z=0;
  E tmp=n;
  while(tmp%p==0) x++,tmp/=p;
  tmp=m;
  while(tmp%p==0) y++,tmp/=p;
  tmp=n-m;
  while(tmp%p==0) z++,tmp/=p;
  E pq=1;
  for(int j=0; j<q; j++) pq*=p;
  return calcu(n,p,q,pq)*inverse(calcu(m,p,q,pq),pq)%pq*inverse(calcu(n-m,p,q,pq),pq)%pq*ksm(p,x-y-z,pq)%pq;
}

E CRT(E n,E m){
  if(n<0||m<0||n<m) return 0;
  if(n==0||m==0) return 1;
  E ret=0,M=1;
  for(auto p:val) M=M*p;
  for(int i=0; i<(int)divsp.size(); i++){
    E dM=M/val[i];
    ret=(ret+C(n,m,divsp[i].first,divsp[i].second)*dM%M*inverse(dM,val[i])%M)%M;
  }
  return ret;
}

void init(int o,int p){
  mod=p;
  for(int i=2; i*i<=p; i++){
    if(p%i) continue;
    int s=0; int x=1;
    while(p%i==0) x*=i,s++,p/=i;
    val.emplace_back(x);
    divsp.emplace_back(make_pair(i,s));
  }
  if(p>1){
    val.emplace_back(p);
    divsp.emplace_back(make_pair(p,1));
  }
}

int ask(long long n){
  if(n==1) return inverse(2,mod);
  E t1=CRT(2*n-4,n-2)-CRT(2*n-4,n-3)+mod;
  t1%=mod;
  t1=t1*4%mod*(2*n%mod-3)%mod*(2*n%mod-1)%mod;
  t1=t1*ksm(inverse(4,mod),n,mod)%mod;
  return t1;
}