#include <bits/stdc++.h>

using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
int Phi(int n)
{
    int d=2;
    long long r=n;
    while(d*d<=n)
    {
        int exp=0;
        while(n%d==0)
        {
            n/=d;
            exp++;
        }
        if(exp)
            r=r/d*(d-1);
        if(d==2)
            d++;
        else d+=2;
    }
    if(n!=1)
        r=r/n*(n-1);
    return r;
}
int power(long long base,int power,int mod)
{
    long long r=1;
    while(power)
    {
        if(power%2)
        {
            r*=base;
            r%=mod;
        }
        base*=base;
        base%=mod;
        power/=2;
    }
    return r;
}
int main()
{
    int a,n,phi;
    fin>>a>>n;
    phi=Phi(n);
    fout<<power(a,phi-1,n);
    return 0;
}