#include <iostream>
#include <fstream>
#define MOD 2000000000
#define ULL unsigned long long

using namespace std;
ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");
ULL n, a, mod;

ULL pow (ULL a, ULL b){ // se vcalculeaza a la puterea b
    a = a % mod;
    if (b == 0)
        return 1;
    if (b % 2 == 0)
        return pow (a*a, b/2) % mod;
    return pow(a*a, b/2) * a % mod;
}

ULL indicele_lui_euler(){
    ULL e = 1, p, d;
    for (int i=2; i*i<=n; i++){
        d = 0;
        while (n % i == 0){
            n /= i;
            d++;
        }
        if (d >= 1){
            e = e * (i-1) % mod;
            e = e * pow (1LL * i, d-1) % mod;
        }
    }
    if (n > 1){
        e = e * (n-1) % mod;
    }
    return e;
}

int main (){
    in >> a >> n;
    mod = n;
    out << pow (a, indicele_lui_euler()-1) % mod;
    return 0;
}