#include <bits/stdc++.h>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long po(long long nr,long long g){
 long long t=1;
 for(int i=1;i<=g;i++){
   t*=nr;
 }
 return t;
}
long long phi(long long nr){
long long d=2,p,p1=1,z,x=nr;
while(x>1){p=0;z=x;
    while(x%d==0){p++;
                  x/=d;
                 }
    if(z%d==0){p1*=(d-1)*po(d,p-1);}
    d++;
    if(x>1&&d*d>x){d=x;}
}
return p1;
}
int main()
{int n,m;
 long long phinr,s=1;
 f>>n>>m;
 phinr=phi(m)-1;
 while(phinr){
    if(phinr&1)s=(s*n)%m;
    n=(n*n)%m;
    phinr>>=1;
 }
 g<<s;
}