RT，代码中 a 和 m 数组（在 $53$ 行）是我用来跑 CRT 的，由于这题同余方程只有四个，所以它们的下标开到 $4$ 理论上就够了

但是我开到 $5$，25pts，大红大紫

我试着把这两个数组开大一点，开到 $1000$，35pts

开到 $5000$，70pts

开到 $10000$，90pts

开到 $15000$，AC

Why???

（P.S. 这两个数组下面紧接着是 CRT 函数，在 main 函数里面预处理出了这两个数组之后调用了 CRT）

#include <cstdio>
#include <cmath>
#define int long long

using namespace std;

struct pair{
	int x,y;
};

pair exgcd(int a,int b){
	if(!b) return (pair){1,0};
	pair k=exgcd(b,a%b);
	return (pair){k.y,k.x-a/b*k.y};
}

int inv(int x,int k){
	return (exgcd(x,k).x%k+k)%k;
}

int d_[]={0,2,3,4679,35617};

int n,d[5000000],cnt;

void fuck_divisor(){
	int sqr = sqrt(n);
	for(int i=1;i<=sqr;++i) if(n%i==0){
		d[++cnt]=i;
		if(n/i!=i) d[++cnt]=n/i;
	}
}

int ftr[5000000],k;

int c(int a,int b){
	return ftr[a]*inv(ftr[a-b],k)%k*inv(ftr[b],k)%k;
}

int C(int a,int b){
	return b?c(a%k,b%k)*C(a/k,b/k)%k:1;
}

int fuck(){
	ftr[0]=1;
	for(int i=1;i<=k;++i) ftr[i]=ftr[i-1]*i%k;
	int res=0;
	for(int i=1;i<=cnt;++i) res=(res+C(n,d[i]))%k;
	return res;
}

const int M=999911658;

int a[15000],m[15000];

int CRT(){
	int res=0;
	for(int i=1;i<=4;++i) res+=a[i]*(M/m[i])*inv(M/m[i],m[i]);
	return (res%M+M)%M;
}

int ksm(int x,int p){
	int res=1;
	while(p){
		if(p&1) res=res*x%(M+1);
		x=x*x%(M+1);p>>=1;
	}
	return res;
}

signed main()
{
	int g;scanf("%lld%lld",&n,&g);
	if(g%(M+1)==0) return !putchar('0');
	fuck_divisor();
	for(int i=1;i<=4;++i) k=m[i]=d_[i],a[i]=fuck();
	printf("%lld",ksm(g,CRT()));
}