#include <iostream>

using namespace std;
 long long int euler(long long int n){
   long long 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 p,long long int m){
long long int sol=1;
long long int i;
for (i = 0; (1<<i) <= p; ++ i)  // Luam toti biti lui p la rand
	{
		if ( ((1<<i) & p) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
			sol= (sol * a) % m;

			a=(a * a) % m; // Inmultim a cu a ca sa obtinem n^(2^(i+1))
			//cout<<(1<<i)<<" "<<a<<" "<<sol<<endl;
	}
	return sol;
}

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


    return 0;
}