本地，luogu全wa，loj可过？？？？呜呜呜。

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
#define int long long
LL read() {
	LL x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 4e6 + 100;
LL mod[6] = {999911659,2,3,4679,35617};
LL g,n,fac[N][6],A[6];
LL qpow(LL a,LL b,LL p) {
	LL x = 1;
	for(;b;b>>=1,a = a * a % p) {
		if(b&1) x = x * a % p;
	}
	return x;
}
LL C(LL a,LL b,LL p) {
	if(b > a) return 0;
	return fac[a][p] * qpow(fac[a-b][p],mod[p]-2,mod[p]) % mod[p] * qpow(fac[b][p],mod[p]-2,mod[p]) % mod[p];
}
LL lucas(LL a,LL b,LL p) {
	if(!b) return 1;
	return lucas(a/mod[p],b/mod[p],p) * C(a%mod[p],b%mod[p],p) % mod[p];
}
void solve(int k) {
	for(int i = 1;i < 5;i++) {
		A[i] = (A[i] + lucas(n,k,i)) % mod[i];
	}
}
void exgcd(LL a,LL b,LL &x,LL &y) {
	if(!b) {x = 1;return;}
	exgcd(b,a%b,x,y);
	LL t = x;
	x = y;
	y = t - (a/b) * y;
}
LL crt() {
	LL res = 0;
	for(int i = 1;i < 5;i++) {
		LL x,y;
		LL tmp = (mod[0] - 1) / mod[i];
		exgcd(mod[i],tmp,x,y);
		res = (res + y * A[i] % (mod[0] - 1) * tmp) % (mod[0] - 1);
	}
	return (res + mod[0] - 1) % (mod[0] - 1);
}
signed main() {
	n = read();g = read();
	for(int x = 1;x < 5;x++)
        {
	      fac[1][x]=fac[0][x]=1;
	      for(int i=2;i < mod[x];++i)
	      fac[i][x] = fac[i-1][x]*i % mod[x];
        }
	if(g % (mod[0]) == 0) {puts("0");return 0;}
	for(int i = 1;i * i <= n;i++) {
		if(n%i) continue;
		solve(i);
		if(n/i != i) solve(n/i); 
	}
	LL ans = crt();
	cout << ans << endl;
	ans = qpow(g,ans,mod[0]);
	cout << ans << endl;
//	cout<<1<<endl;
	system("pause");
	return 0;
}