#include <iostream>
#include <fstream>

using namespace std;

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

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

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

int main()
{
    long long A, N, X;
    fin >> A >> N;
    long long e = eul(N);
    fout << exp(e - 1, A, N);
    return 0;
}