#include <bits/stdc++.h>
#define in "inversmodular.in"
#define out "inversmodular.out"
using namespace std;
ifstream fin (in);
ofstream fout (out);

int n,m;

long long phi(long long nr)
{
    long long cr = nr;
    int i;

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

int main()
{
    long long exp,nr,crt;
    long long p;

    fin >> n >> m;
    exp = phi(m) - 1;
    nr = n;
    crt = 1;
    for (p = 1; p <= exp; p <<= 1)
    {
        if (p & exp) crt = (crt*nr) % m;
        nr = (nr*nr) % m;
    }

    fout << crt << "\n";

    fin.close();
    fout.close();
    return 0;
}