#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;

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

long long lgput(long long a, long long b, long long mod) {
    long long p = 1;
    while (b) {
        if (b % 2) p = (p * a) % mod, b--;
        a = (a * a) % mod;
        b /= 2;
    }
    return p;
}
int main()
{
    long long a, b;
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    fin >> a >> b;
    long long x = get_phi(b);
    fout << lgput(a, x - 1, b);
    return 0;
}