只过了13这个特判点其余全部re了

#include<bits/stdc++.h> 
#define ull unsigned long long
#define lch(x) t[x].s[0] 
#define rch(x) t[x].s[1]
#define INF 0x3f3f3f3f
#define ll long long 
#define lll __int128
#define re register
#define inl inline
#define N 500500
#define rx x<<1|1
#define lx x<<1
using namespace std;

const int mod = 999911659 ;
int a[] = {2,3,4679,35617} ,anx[N];
ll f[4][N] ,g[4][N] ;
int n ,q ;

inline int read(){
	int w = 1 ,s = 0;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch=='-') w = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		s = (s<<3)+(s<<1)+ch-'0';
		ch = getchar();		
	}
	return w*s;
}

ll qpow(ll x,ll k,ll mod){
	ll res = 1;
	while(k){
		if(k & 1) res = res * x % mod ;
		x = x * x % mod ;
		k >>= 1;
	}
	return res;
}

inl int init(){
	for(int i = 0;i < 4;i ++ ){
		f[i][0] = g[i][0] = 1;
		int mod = a[i] ;
		for(int j = 1;j <= a[i];j ++ ){
			f[i][j] = f[i][j-1] * j % mod;
			g[i][j] = g[i][j-1] * qpow(j,mod-2,mod) % mod;
		}
	}
}

ll get(int x,int y,int k,int mod){
	if(y > x) return 0;
	return f[k][x] * g[k][y] % mod * g[k][x-y] % mod;
}

ll lucas(int x,int y,int k,int mod){
	if(!y) return 1;
	return lucas(x/mod,y/mod,k,mod) * get(x%mod,y%mod,k,mod) % mod;
}

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

inl ll CRT(){
	ll ans = 0;
	int md = 999911658;
	for(int i = 0;i < 4;i ++ ){
		int k = md / a[i] ;
		ll x ,y ;
		exgcd(k,a[i],x,y) ;
		x = (x % a[i] + a[i]) % a[i] ;
		ans = (ans + x * k % md * anx[i] % md) % md;
	}
	return (ans % md + md) % md;
}

inl void work(){
	init();
	
	for(int i = 1;i * i <= n;i ++ ){
		if(n % i == 0){
			for(int j = 0;j < 4;j ++ ) {
				anx[j] = ((lucas(n,i,j,a[j]) + anx[j]) % a[j] +a[j]) % a[j];
			}
			if(n / i != i){
				for(int j = 0;j < 4;j ++ ) {
					anx[j] = ((lucas(n,n/i,j,a[j]) + anx[j]) % a[j] +a[j]) % a[j];
				}
			}
		}
	}
	
	ll res = CRT() ;
	cout << qpow(q,res,mod);
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> q ;
	
	if(q == mod) {
		cout << 0 ;
		return 0;
	}
	
	work();
}