#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int n,i,a,t;
int ridica(int a,int n)
{
    if(n==0)
        return 1;
    else
    if(n%2==1)
        return a*ridica(a,n-1);
    else
    {
        int p;
        p=ridica(a,n/2);
        return p*p;
    }
}
int main()
{
    fin>>a>>n;
    t=n;
    for(i=2;i*i<=n;i++)
    if(n%i==0)
    {
        t=t*(i-1)/i;
        while(n%i==0)
            n/=i;
    }
    if(n!=1)
        t=t*(n-1)/n;
    t--;
    fout<<ridica(a,t)%n;
    return 0;
}