#include <fstream>
#include <vector>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");


vector<int> d;
int n, m, i, sol, a, MOD;
int main()
{
    f>>a>>n;
    MOD=m=n;
    for(i=2;i*i<=m;i++)
        if(m%i==0)
        {
            d.push_back(i);
            while(m%i==0)
                m/=i;
        }
    if(m>1)
        d.push_back(m);
    for(auto it:d)
        n=n/it*(it-1);
    n--;
    sol=1;

    for(;n;n/=2)
    {
        if(n%2==1)
            sol=(1LL*sol*a)%MOD;
        a=(1LL*a*a)%MOD;
    }
    g<<sol;
    return 0;
}