#include <iostream>
#include <fstream>

using namespace std;
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
int e[200000001];
 int euler(int n){

    for(int i=1;i<=n;i++)
        e[i]=i;
    for(int i=2;i<=n;i++)
        if(e[i]==i)///este prim
            for(int j=i;j<=n;j+=i)
                e[j]=(e[j]/i)*(i-1);

    return e[n];

 }

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;
}