#include <fstream>

using namespace std;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

long long lg_put(long long a,long long b,long long m)
{
    long long p=1;
    while(b)
    {
        if(b%2==0)
        {
            a=(a*a)%m;
            b=b/2;
        }
        else
        {
            b--;
            p=(p*a)%m;
        }
    }
    return p%m;
}

long long phi(long long n)
{
    long long d=2,euler=n;
    while(d*d<=n)
    {
        if(n%d==0)
            euler=euler/d*(d-1);
        while(n%d==0)
            n=n/d;
        d++;
    }
    if(n>1)
        euler=euler/n*(n-1);
    return euler;
}

int main()
{
    long long a,m;
    cin>>a>>m;
    cout<<lg_put(a%m,(phi(m)-1)%m,m);
    return 0;
}