#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long n,ct;
long long fi(long long n)
{
    int d=2;
    long long ans=n;
    while(n>1 and d*d<=n)
    {
        while(n%d==0)
            ans=1LL*ans*(d-1)/d%ct, n/=d;
        d++;
    }
    if(n!=1)
        ans=1LL*ans*(n-1)/n;
    return ans;
}
long long put(long long a, long long b)
{
    a%=ct;
    if(b==0)
        return 1;
    if(b%2)
        return 1LL*a*put(a,b-1)%ct;
    long long p=put(a,b/2);
    return 1LL*p*p%ct;
}
int main()
{
    long long a;
    cin>>a>>n;
    ct=n;
    cout<<put(a,fi(n)-1)%ct;
}