#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    long long x, n, pr, i, p, cn;
    fin>>x>>n;
    i=2;
    pr=n;
    cn=n;
    while(i*i<=n){
        if(n%i==0){
            pr/=i;
            pr*=(i-1);
            while(n%i==0){
                n/=i;
            }
        }
        i++;
    }
    if(n!=1){
        pr/=n;
        pr*=(n-1);
    }
    pr--;
    p=1;
    while(pr>0){
        if(pr%2==1){
            p*=x;
            p%=cn;
        }
        x*=x;
        x%=cn;
        pr/=2;
    }
    fout<<p%cn<<'\n';
    return 0;
}