题目链接:http://codeforces.com/problemset/problem/603/B
题目大意
给定一种函数关系，
f(x*k%p)=k*f(x)%p,
值域和定义域都是0到p-1，
问这样的函数关系有多少种。
题目分析
这题是数论题，并且参杂些细节，
首先对于0这个位置，如果k为1，那么有p种f（0），
否则只有一种，那就是0，
我们可以把0这个位置独立出来不难发现。
下面分析任意x>=1,由于k的范围k肯定和p互质，
那么就有定理:k^(p-1)%p=1,由于范围不是特别大，
我们只要暴力枚举k几次幂的时候模p为1，
我们要求其最少的幂次数所以需要枚举，上面式子只能保证等式成立，
（事实上我有种复杂度更低的分解质因数的想法。。。）
然后可以发现每个数都有这样一个循环节，大小就是上面求的幂次，
不难发现p-1是整除这个幂次的，我们用这个除数来组合函数数量关系，
至于整除的合理性，我们可以利用上面的等式来分析，具体过程就不列举了，
不难想到的。
那么到这里这题思路就很清晰了。
详见代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll unsigned long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
int mod=1e9+7;
const int maxn=30+10;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
给定一种函数关系，
f(x*k%p)=k*f(x)%p,
值域和定义域都是0到p-1，
问这样的函数关系有多少种。题目分析：
这题是数论题，并且参杂些细节，
首先对于0这个位置，如果k为1，那么有p种f（0），
否则只有一种，那就是0，
我们可以把0这个位置独立出来不难发现。
下面分析任意x>=1,由于k的范围k肯定和p互质，
那么就有定理:k^(p-1)%p=1,由于范围不是特别大，
我们只要暴力枚举k几次幂的时候模p为1，
我们要求其最少的幂次数所以需要枚举，上面式子只能保证等式成立，
（事实上我有种复杂度更低的分解质因数的想法。。。）
然后可以发现每个数都有这样一个循环节，大小就是上面求的幂次，
不难发现p-1是整除这个幂次的，我们用这个除数来组合函数数量关系，
至于整除的合理性，我们可以利用上面的等式来分析，具体过程就不列举了，
不难想到的。
那么到这里这题思路就很清晰了。
详见代码。
*/
ll p,k,cnt=1,tk;
int main(){cin>>p>>k;tk=k;if(k) while(k%p!=1)k=k*tk%p,cnt++;if(tk!=1) cout<<powmod(p,(p-1)/cnt)<<endl;else cout<<powmod(p,(p-1)/cnt)*p%mod<<endl;return 0;
}