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

long long get_phi(long long nr) {
    long long  x = nr - 1;
    long long rad = sqrt(nr);
    for (long long i = 2; i <= rad; ++i) {
        if (nr % i == 0) {
            if (i != rad) x -= 2;
            else x -= 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;
}