#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int N, MOD;
int getphi(int nr)
{
    int curr=nr;

    for(int i=2;i*i<=nr;i++)
    {
        if(nr%i==0)
        {
            while(nr%i==0)
                nr/=i;
            curr=(curr/i)*(i-1);
        }
    }
    if(nr!=1)
        curr=(curr/nr)*(nr-1);

    return curr;
}
long long lg_power(long long nr, long long exp)
{
    if(exp==0)
        return 1;

    if(exp%2==0)
    {
        long long half=lg_power(nr, exp/2);
        return (half*half)%MOD;
    }

    if(exp%2==1)
        return (nr*(lg_power(nr, exp-1)))%MOD;
}
int main()
{
    fin>>N>>MOD;

    int power=getphi(MOD)-1;

    fout<<lg_power(N, power)%MOD;
    return 0;
}