#include <fstream>

using namespace std;

int a,n;

inline int phi (int n)
{
    int p,fi;
    fi=n;
    p=2;
    if(n%p==0)
    {
        fi=fi/p*(p-1);
        while(n%p==0)
            n/=p;
    }
    p=3;
    while(n>1&&p*p<=n)
    {
        if(n%p==0)
        {
        fi=fi/p*(p-1);
        while(n%p==0)
            n/=p;
        }
        p+=2;
    }
    if(n>1) fi=fi/n*(n-1);
    return fi;
}

inline int Pw(int a,int n,int mod)
{
    int p=1;
    while(n)
    {
        if(n%2==1)
        {
            p=(1LL*p*a)%mod;
            n--;
        }
        a=(1LL*a*a)%mod;
        n/=2;
    }
    return p;
}

int main()
{
    int p;
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    fin>>a>>n;
    p=phi(n)-1;
    fout<<Pw(a,p,n)<<"\n";
    fout.close();
    return 0;
}