#include <cstdio>
using namespace std;
typedef long long i64;

inline int phi(int n){
    int acc=0;
    i64 i, cn = n, ans = n;

    while(n%2==0){
        ++acc;
        n/=2;
    }
    if(acc)
        ans=ans/2;
    for(i=3; i*i<=n; i+=2) {
        acc=0;
        while(n%i==0) {
            n/=i;
            ++acc;
        }
        if(acc)
            ans=ans*(i-1)/i;
    }
    if(n>1)
        ans=ans*(n-1)/n;
    return ans;
}
int exp(i64 b, i64 e, int mod){
    i64 ans=1;

    while(e){
        if(e&1)
            ans=ans*b%mod;
        e>>=1;
        b=b*b%mod;
    }

    return int(ans%mod);
}

int main(void){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int n,k;
    scanf("%d%d",&n,&k);
    printf("%d",exp(k,phi(n)-1,n));
    return 0;
}