#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long N, M;
int prim(long long x)
{
    if(x < 0)
        return 0;
    if(x == 2)
        return 1;
    if(x % 2 == 0)
        return 0;
    for(int d = 3; d * d <= x; d += 2)
    {
        if(x % d == 0)
            return 0;
    }
    return 1;
}
int ridic(long long x, long long p, long long m)
{
    long long rez = 1;
    while(p > 0)
    {
        if(p % 2 == 1)
            rez = ( (rez % m) * (x % m) ) % m;
        x = ( (x % m) * (x % m) ) % m;
        p /= 2;
    }
    return rez;
}
void citire()
{
    fin>>N>>M;
    long long putere;
    if(prim(M) == 1)
    {
        putere = M - 2;
    }
    else
        putere = M - 1;
    fout<<ridic(N, putere, M);
}
int main()
{
    citire();
    return 0;
}
/***

Daca N este prim ridicam la puterea N - 2
Contrar ridicam la puterea N - 1;
*/