#include <iostream>

using namespace std;
int euler(int n){
     int p=1,cn=n,d;
    for(d=2;d*d<=n;d++){
        if(n%d==0){
            p=p*(d-1);
        cn=cn/d;
        while(n%d==0){
            n=n/d;
        }
        }

    }
    if(n>1){
        cn=cn/n;
    p=p*(n-1);}
      return cn*p;
}
long long int exponentiere(long long int a,long long int b,int m){
long long putere=1;
a=a%m;
while(b>0){
    if(b%2!=0){
        putere=putere*a%m;
    }
    a=a*a%m;
    b=b/2;
}

return putere;
}

int main()
{ int a,n,f;
cin>>a>>n;
f=euler(n);
cout<<exponentiere(a,f-1,n);


    return 0;
}