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

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