#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;
    bool p=1;
    long long d;
    for(d=2;d*d<=n;d++)
    {
        if(n%d==0)
        {   p=0;
            eul=eul*(d-1)/d;

            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;
}