#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long a,n;

long long raisePower(long long nr, long long p)
{
    long long sol=1;
    for(long long i=0;(1<<i)<=p;++i)
    {
        if(((1<<i) & p)>0)
            sol=(sol*nr)%n;

        nr=(nr*nr)%n;
    }
    return sol%n;
}

int main()
{
    fin>>a>>n;

    int cn = n;
    long long phi=n;
    for(long long i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            while(n%i==0)n/=i;
            phi = (phi/2)*(i-1);
        }
    }
    if(n!=1)
        phi=phi/n*(n-1);

    n=cn;
    fout<<raisePower(a,phi-1);

    return 0;
}