#include <iostream>
#include<fstream>
using namespace std;ifstream fin("inversmodular.in");ofstream fout("inversmodular.out");
long long a,b;
int calc(int n){int ph=n;for(int i=2;i*i<=n;i++)if(n%i==0){while(n%i==0)n/=i;
ph=ph/i*(i-1);}if(n>1)ph=ph/n*(n-1);
return ph;}
int exp(int a,int b,int mod){int rez=1;
while(b>0){if(b&1){rez=(1ll*rez*a)%mod;b--;}
    a=(1ll*a*a)%mod;b/=2;
}return rez;
}
int main()
{fin>>a>>b;fout<<exp(a,calc(b)-1,b);
    return 0;
}