#include <iostream>
#include <fstream>

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

 }

int main()
{
    unsigned int n,p,a,i;
    long long sol=1;
    fi>>a>>n;
    p=euler(n)-1;
    for(i=0;(1<<i)<=p;i++)
    {
        if(((1<<i)&p)>0)
            sol=(sol*a);
         a=(a*a);
    }
    fo<<sol%n;
    fi.close();
    fo.close();


    return 0;
}