#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream in ("inversmodular.in");
ofstream out("inversmodular.out");
int a, n, mod, i, diviz=1;
int explog(int x1, int n1)
{
    int p=1;
    int x=x1;
    while(n1>0)
    {
        if(n1%2==1)
        {
            p=p*x%mod;
            n--;
        }
        x=x*x%mod;
        n1/=2;
    }
    return p;
}
int main()
{
    in>>a>>n;
    mod=n;

    for(i=2; i*i<=n; i++)
    {
        if(n%i==0) diviz+=2;
    }
    if((i-1)*(i-1)==n) diviz--;
    diviz=n-diviz;
    out<<explog(a, diviz-1);
    return 0;
}