#include <iostream>
#include <fstream>


using namespace std;

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

int n , m;

int euler (int a)
{
    int phi = a;
        for (int d = 2 ; d * d <= a ; d++)
        {
            if (a % d == 0)
            {
                phi = phi / d * (d - 1);
              while (a % d == 0)
                a = a / d;
            }
        }
    if (a > 1)
        phi = phi / a * (a - 1);
    return phi;
}

int rid (int a , int b)
{
    int rez = 1;
    while (b)
    {
        if (b % 2 == 1)
            rez = (1LL * rez * a) % m;
            a = (1LL * a * a) % m;
            b = b / 2;
    }
    return rez;
}

int main()
{
    f >> n >> m;
    g << rid (n , euler (m) - 1) % m;
    return 0;
}