#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long rez=1,a,n,eul;
void citire()
{
    fin>>a>>n;
}
void putere(long long x,long long nr,long long &rez)
{
    while(nr>0)
    {
        if(nr%2==0)
        {
            x=(x*x)%n;
            nr=nr/2;
        }
        else
        {
            rez=(rez*x)%n;
            x=(x*x)%n;
            nr=nr/2;
        }
    }

}
void euler(long long n)
{
    eul=n;
    long long m=n;
    bool p=1;
    long long d;
    if(n%2==0)
    {
        p=0;
        eul=eul/2;
        while(n%2==0)
            n=n/2;

    }

    for(d=3; d+d<=m; d=d+2)
    {
        if(n%d==0)
        {
            p=0;
            eul=eul/d*(d-1);
            while(n%d==0)
            {
                n=n/d;
            }

        }
    }
    if(p==1) eul--;

}
int main()
{
    citire();
    euler(n);
    putere(a,eul-1,rez);
    fout<<rez;

    return 0;
}