#include<fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long int p(long long int a, long long int b){

    if(b==0) return 1;
    if(b==1) return a;
    long long int t=p(a, b/2);
    return t*t*p(a, b%2);

}
long long a, n, v[100000000];
int main(){

    f>>a>>n;
    v[1]=1;
    for(long long int i=2;i<=n;i++){

        v[i]=i-1;

    }
    for(long long int i=2;i<=n;i++){

        for(long long int j=i+i;j<=n;j+=i){

            v[j]-=v[i];

        }

    }
    if(v[n]==n-1) g<<p(a, n-2);
    g<<p(a, v[n]-1)%n;

}