#include <iostream>
#include <fstream>
typedef long long ll;
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

ll getphi(ll x)
{   ll rez=x;
    for(ll i=2;i*i<=x;i++)
    {   if(x%i==0)
        {
            while(x%i==0)x=x/i;
            rez=(rez/i)*(i-1);
        }

    }
    if(x!=1)rez=(rez/x)*(x-1);
    return rez;
}

int main()
{ll a,n,crt,phi;
fin>>a>>n;
crt=1;
phi=getphi(n)-1;
for(ll p=1;p<=phi;p<<=1)
{   if(p & phi){
        crt=(crt*a)%n;
        }
    a=(a*a)%n;
}
fout<<crt;
}