#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int power(long long base,int power,int mod)
{
    long long res=1;
    while(power)
    {
        if(power%2)
        {
            res*=base;
            res%=mod;
        }
        base*=base;
        base%=mod;
        power/=2;
    }
    return res;
}
int main()
{
    int a,n,phi;
    fin>>a>>n;
    phi=n-1;
    for(long long d=2;d*d<=n;d++)
    {
        if(n%d==0)
        {
            phi--;
            if(d*d!=n)
                phi--;
        }
    }
    fout<<power(a,phi-1,n);
    return 0;
}