#include <fstream>
using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");

int Pow(int x, int y, int mod)
{
    if (y==0) return 1;
    if (y==1) return x%mod;
    int p=Pow(x, y/2, mod);
    if (y%2==0) return (1LL*p*p)%mod;
    else return ((1LL*p*p)%mod*x)%mod;
}

int phi(int n)
{
    int d, ct, fi=n;
    d=2;
    while (n!=1)
    {
        ct=0;
        while (n%d==0) {n/=d, ct++;}
        if (ct>0) fi=fi*(d-1)/d;
        if (d*d<n) d++;
        else d=n;
    }
    return fi;
}

int main()
{
    int a, n;
    fin>>a>>n;
    fout<<Pow(a, phi(n)-1, n);
    return 0;
}