#include <bits/stdc++.h>
#define ll unsigned long long

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int n, m;
int ridicare(ll x, int n)
{
    if (n == 1) return x;
    else if (n % 2 == 0) return ridicare((x * x) % m, n / 2);
    else return x * ridicare((x * x) % m, n / 2) % m;
}
int phi(int n)
{
    int i, p = n;
    for (i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            while (n % i == 0)
                n /= i;
            p = p / i * (i - 1);
        }
    if (n != 1) p = p / n * (n - 1);
    return p;
}
int main()
{
    fin >> n >> m;
    fout << ridicare(n, phi(m) - 1);
    return 0;
}