#include<bits/stdc++.h>
#include "pilgrimage.h"
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

int TOT;

char _buf[1<<26],*iS=_buf-1;
#define getchar() (*iS++)
inline int read(){
	char ch=' '; int x=0;
	do{
		ch=getchar();
	}while(ch<'0' || ch>'9');
	do{
		x=x*10+ch-'0';
		ch=getchar();
	}while(ch>='0' && ch<='9');
	return x;
}

void exgcd(int &x,int &y,int a,int b){
	if(!b){
		x=1, y=0;
		return;
	}
	exgcd(x, y, b, a%b);
	// bx+(a-a/b*b)y
	int t=x;
	x=y, y=t-a/b*y;
}
int inv(int x,int mod){
	int t0,t1;
	exgcd(t0,t1,x,mod);
	return (t0%mod+mod)%mod;
}

const int N=1e6+5;

struct Sub{
	int mod,p;
	
	u128 T,T0; int lg,lg0;
	inline int Div(const int &x){
		return T*x>>lg;
	}
	inline int Mod(const int &x){
		return x-mod*Div(x);
	}
	
	struct Int{
		int w,c;
		Int(int x=0){w=x, c=0;}
		Int(int _w, int _c){
			w=_w, c=_c;
		}
	};
	inline Int mul(const Int &A,const Int &B){
		return (Int){ Mod(A.w*B.w), A.c+B.c};
	}
	int qpow(int x,int y){
		int res=1;
		while(y){
			if(y%2) res=Mod(res*x);
			x=Mod(x*x);
			y/=2;
		}
		return res;
	}int inv(int x){return qpow(x, mod/p*(p-1)-1);}

	vector<Int> fac;
	void init(int _mod){
		mod=_mod;
		
		p=0;
		rep(i,2,mod){
			if(mod%i==0){
				p=i;
				break;
			}
		}
		assert(p!=0);
		
		lg=__lg(mod)+64;
		T=(((u128)1<<lg)+mod-1)/mod;
		
		fac.resize(mod);
		fac[0]=1;
		rep(i,1,mod-1){
			if(i%p==0){
				fac[i]=fac[i-1];
			}
			else{
				fac[i]=mul(fac[i-1], i);
			}
		}
	}
	Int Fac(int x){
		Int res=1;
		while(x>=p){
			int nxt=x/p;
			Int c=(Int){ (Div(x)%2? mod-1: 1), nxt}, g=fac[Mod(x)];
			res=(Int){ Mod(c.w*g.w*res.w), c.c+g.c+res.c};
			x=nxt;
		}
		res=mul(res, fac[x]);
		return res;
	}
	int C(int n){
		Int a=Fac(n*2), b=Fac(n);
		Int pr={Mod( a.w*inv( Mod(b.w*b.w) ) ), a.c-b.c*2};
		int res=pr.w;
		while(res && pr.c){
			pr.c--;
			(res*= p )%=mod;
		}
		return res;
	}
};


int mod, phimod, i4;
int qpow(int x,int y){
	if(y>=phimod){
		y%=phimod;
	}
	int res=1;
	while(y){
		if(y%2) res=res*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return res;
}
vi Mod, K;
vector< Sub > S;
void Init(){
	i4=inv(4,mod);
	phimod=mod;
	int tmp=mod;
	for(int i=2;i*i<=tmp;i++){
		if(tmp%i==0){
			phimod=phimod/i*(i-1);
			Mod.pb(1);
			while(tmp%i==0){
				Mod.back()*=i;
				tmp/=i;
			}
		}
	}
	if(tmp!=1){
		phimod=phimod/tmp*(tmp-1);
		Mod.pb(tmp);
	}
	rep(i,0,(int)Mod.size()-1){
		K.pb( (mod/Mod[i])*inv(mod/Mod[i],Mod[i])%mod );
	}
	rep(i,0,(int)Mod.size()-1){
		S.pb({});
		S[i].init(Mod[i]);
	}
}
void Ask(){
	int n=read();
}
void init(signed o,signed p){
	mod=p;
	Init();
}
signed ask(int n){
	int res=0;
	rep(i,0,(int)Mod.size()-1){
		(res+= K[i]*S[i].C(n) )%=mod;
	}
	res= n%mod*res%mod*qpow(i4,n)%mod; 
	return res;
}

answer.code:51:9: error: ‘u128’ does not name a type
   51 |         u128 T,T0; int lg,lg0;
      |         ^~~~
answer.code: In member function ‘long long int Sub::Div(const long long int&)’:
answer.code:53:24: error: ‘T’ was not declared in this scope
   53 |                 return T*x>>lg;
      |                        ^
answer.code: In member function ‘void Sub::init(long long int)’:
answer.code:93:17: error: ‘T’ was not declared in this scope
   93 |                 T=(((u128)1<<lg)+mod-1)/mod;
      |                 ^
answer.code:93:22: error: ‘u128’ was not declared in this scope
   93 |                 T=(((u128)1<<lg)+mod-1)/mod;
      |                      ^~~~
answer.code:93:27: error: expected ‘)’ before numeric constant
   93 |                 T=(((u128)1<<lg)+mod-1)/mod;
      |                           ^
answer.code:93:20: note: to match this ‘(’
   93 |                 T=(((u128)1<<lg)+mod-1)/mod;
      |                    ^
answer.code:93:44: error: expected ‘)’ before ‘;’ token
   93 |                 T=(((u128)1<<lg)+mod-1)/mod;
      |                                            ^
answer.code:93:19: note: to match this ‘(’
   93 |                 T=(((u128)1<<lg)+mod-1)/mod;
      |                   ^