#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
typedef long long ll;
ll pw(ll x, ll y, ll mod){
    if(mod<2) return 0;
    ll ans=1;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1)
            ans=ans*x%mod;
    return ans;
}
ll phi(ll x){
    if(x==0) return 0;
    ll ans=1,d=2;
    if(x%d==0){
        x/=d,ans*=(d-1);
        while(x%d==0)
            x/=d,ans*=d;
    }
    for(d=3;d*d<=x;d+=2){
        if(x%d==0){
            x/=d,ans*=(d-1);
            while(x%d==0)
                x/=d,ans*=d;
        }
    }
    if(x>1) ans*=(x-1);
    return ans;
}
int main()
{
    ll x,y;
    fin>>x>>y;
    fout<<pw(x,phi(y)-1,y);
    return 0;
}