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

long long Mod,ny2;
int pri[30],pw[30],gl[30],phi[30],tot,Phi;
int jc[30][1000010];
long long a[30],P[30];
long long qpow(long long a,long long p,int Mod)
{
	long long ret=1;
	for(;p;p>>=1,(a*=a)%=Mod)
		if(p&1) (ret*=a)%=Mod;
	return ret;
}
long long yzcnt(long long n,int p)
{
	long long ret=0;
	while(n) ret+=(n/=p);
	return ret;
}
long long S(long long n,int ind)
{
	if(n==0) return 1;
	return S(n/pri[ind],ind)*1ll*qpow(jc[ind][gl[ind]],n/gl[ind],gl[ind])%gl[ind]*jc[ind][n%gl[ind]]%gl[ind];
}
long long ExLucas(long long n,long long m)
{
	for(int i=1;i<=tot;i++)
	{
		a[i]=S(n,i)*qpow(S(m,i),phi[i]-1,gl[i])%gl[i]*qpow(S(n-m,i),phi[i]-1,gl[i])%gl[i];
		a[i]=a[i]*qpow(pri[i],yzcnt(n,pri[i])-yzcnt(m,pri[i])-yzcnt(n-m,pri[i]),gl[i])%gl[i];
		P[i]=gl[i];
	}
	long long ret=0;
	for(int i=1;i<=tot;i++)
		(ret+=a[i]*(Mod/P[i])*qpow(Mod/P[i],phi[i]-1,P[i]))%=Mod;
	return ret;
}
long long rem[3100];bool aaa;
void init(int o, int p)
{
	if(o==2)
	{
		aaa=true;
		memset(rem,-1,sizeof(rem));
	}
	Mod=p;
	for(int i=2;i*i<=p;i++)
	{
		if(p%i==0)
		{
			pri[++tot]=i;
			while(p%i==0)
				pw[tot]++,p/=i;
		}
	}
	if(p!=1) pri[++tot]=p,pw[tot]=1;
	Phi=1;
	for(int i=1;i<=tot;i++)
	{
		jc[i][0]=1;
		gl[i]=qpow(pri[i],pw[i],Mod+1);
		phi[i]=gl[i]-gl[i]/pri[i];
		Phi*=phi[i];
		for(int j=1;j<=gl[i];j++)
		{
			if(j%pri[i]) jc[i][j]=jc[i][j-1]*1ll*j%gl[i];
			else jc[i][j]=jc[i][j-1];
		}	
	}
	ny2=qpow(2,Phi-1,Mod);
	if(aaa)
		for(int n=1;n<=3000;n++)
			rem[n]=n%Mod*ExLucas(2*n-1,n-1)%Mod*qpow(qpow(2,2*n-1,Mod),Phi-1,Mod)%Mod;
	return;
}

int ask(long long n)
{
	long long ans=0;
	if(aaa) return rem[n];
	ans=n%Mod*ExLucas(2*n-1,n-1)%Mod;
	ans*=qpow(ny,2*n-1,Mod);
	return ans%Mod;
}

answer.code: In function ‘int ask(long long int)’:
answer.code:83:19: error: ‘ny’ was not declared in this scope; did you mean ‘n’?
   83 |         ans*=qpow(ny,2*n-1,Mod);
      |                   ^~
      |                   n