#include <bits/stdc++.h>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long n,p,a,cn,var,fi;

long long  lgput(long long x,long long y)
{
    if(y==1)
        return x;
    if(y%2==1)
        return lgput(x,y-1)*x;
    else
        return lgput(x,y/2)*lgput(x,y/2);
}
int main()
{
    f>>a>>n;
    cn=n;
    fi=1;
    for(int d=2;d*d<=n;d++)
    {
        var=1;
        while(n%d==0)
        {
            var*=d;
            n/=d;
        }
        fi*=var-var/d;
    }
    if(cn!=1)
        fi=n-1;
    fi=fi-1;
    g<<lgput(a,fi)%n;
    return 0;
}