#include <iostream>
#include <fstream>

using namespace std;
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
#define LL long long
LL euler(LL n){
	LL c=n;
    for(LL i=2;i*i<=n;++i)
        {
			if(n%i==0)
				{
					while(n%i==0)n/=i;
					c = (c/i)*(i - 1);
				}
		}
			if(n!=1)c=c/n*(n-1);
    return c;

 }

int main()
{
    LL n,p,j,k,a,sol=1;
    fi>>a>>n;
    p=euler(n)-1;
    for(j=0;(1<<j)<=p;++j)
    {
        if(((1<<j)&p)>0)
            sol=sol*a;
        a=a*a;
    }
    fo<<sol%n<<endl;







    return 0;
}