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

#define ll long long

ll exponentiation_by_sq(ll n, ll p, ll orig_n) {
    if (p == 0)
        return 1;
    if (p % 2 == 0)
        return exponentiation_by_sq(n * n % orig_n, p / 2, orig_n) ;
    if (p % 2 == 1) {
        return n * exponentiation_by_sq(n * n %orig_n, (p - 1) / 2, orig_n) % orig_n;
    }
    return 1;
}

ll phi(int n) {
    ll phi = n;

    for (int p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            phi -= phi / p;
        }
    }

    if (n > 1)
        phi -= phi / n;

    return phi;
}

int main() {
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");

    ll a, n;

    fin>>a>>n;

    fout<<exponentiation_by_sq(a, phi(n) - 1, n);

    return 0;
}