#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long p;
long long put(long long a,long long b)
{
    if(b==0)
    {
        return 1%p;
    }
    if(b%2==0)
    {
        long long f = put(a,b/2)%p;
        return ((f%p)*(f%p))%p;
    }
    return (a%p)*(put(a,b-1)%p)%p;
}
long long phi(long long n)
{
    long long r=n,d=2;
    while(n>1)
    {
        if(n%d==0)
        {
            r=r/d*(d-1);
            while(n%d==0)
                n/=d;
        }
        d++;
        if(d*d>n)
            d=n;
    }
    return r;
}
int main()
{long long x,n;
cin>>x>>n;p=n;
n=phi(p)-1;
cout<<put(x,n);
    return 0;
}