b数组开小就会re。。 在本地oj上提交发现厌氧……

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=999911659;
vector <int>a;
int jcqm[40005][5],ny[40005][5],jcny[40005][5];
int b[5];
int ys[5]={0,2,3,4679,35617};
int x,y;
void gan()
{
	for(int j=1;j<=4;j++)
	{
	int m=ys[j];
	ny[1][j]=1;
	for(int i=2;i<=m-1;i++)
    ny[i][j]=(m-m/i)*ny[m%i][j]%m;
	jcqm[0][j]=1;jcny[0][j]=1;
	for(int i=1;i<=ys[j];i++)
	{
		jcqm[i][j]=jcqm[i-1][j]*i%m;
		jcny[i][j]=jcny[i-1][j]*ny[i][j]%m;
	}
	}
} 
inline int ksm(int a,int b,int c)
{
	int ans=1;
	a%=c;
	while(b)
	{
		if(b%2)ans=(ans*a)%c;
		b/=2;
		a=(a*a)%c;
	 } 
	return ans;
}
inline int cnm(int n,int m,int q)
{
	return jcqm[n][q]*(jcny[m][q]*jcny[n-m][q]%ys[q])%ys[q];
}
inline int lks(int n,int m,int q)
{
	if(n<m)return 0;
	if(m==0)return 1;
	return cnm(n%ys[q],m%ys[q],q)*lks(n/ys[q],m/ys[q],q)%ys[q];
}
inline int exgcd(int a,int b)
{
	if(b==0)
	{
		x=1;y=0;
		return a;
	}
	int gcd=exgcd(b,a%b);
	int q=x;
	x=y;
	y=q-(a/b)*x;
	return gcd;
}
inline int crt()
{
	int ans=0;
	for(int i=1;i<=4;i++)
	{
		x=0;y=0;
		int gcd=exgcd((mod-1)/ys[i],ys[i]);
		x%=ys[i];if(x<ys[i])x+=ys[i];
		ans=(ans+x*b[i]*((mod-1)/ys[i])%(mod-1))%(mod-1);
	}
	ans%=(mod-1);
	return ans;
}
signed main()
{
	int n,g;
	cin>>n>>g;
	if(g%mod==0)
	{
		cout<<0;return 0;
	}
	gan(); 
	for(int i=1;i<=sqrt(n);i++)
	if(n%i==0)
	{
		a.push_back(i);
		if(n/i!=i)a.push_back(n/i);
	}
	for(int i=1;i<=4;i++)
	{
		int an=0;
		for(int j=0;j<a.size();j++)
	   	an=(an+lks(n,a[j],i))%ys[i];
		b[i]=an; 
	}
	cout<<ksm(g,crt(),mod);
	return 0;
}