#include <iostream>
#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

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

long long exp(long long A , long long n, long long modulo)
{
    long long P = 1;
    while(n)
    {
        if(n % 2 == 1)
        {
            P *= A;
            P%=modulo;
        }
        A *= A;
        A%=modulo;
        n /= 2;
    }
    return P;
}

int main()
{
    long long a, N;
    f >> a >> N;
    long long p= phi(N);
    g << exp(p-1,a,N);
    return 0;
}