#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=1,d=2;
    fin>>a>>n;
    int cpy=n;
    while(d*d<=cpy)
    {
        int exp=0;
        while(cpy%d==0)
        {
            cpy/=d;
            exp++;
        }
        phi=phi*(exp+1);
        if(d==2)
            d++;
        else d+=2;
    }
    if(cpy!=1)
        phi*=2;
    phi=n-phi+1;
    fout<<power(a,phi-1,n);
    return 0;
}