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

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

long long n, a;

long long inversmodular(long long a, long long n, long long MOD) {
    long long p = 1;
    while (n) {
        if (n%2) {
            p = p*a;
            p %= MOD;
        }
        n/=2;
        a = a*a;
        a %= MOD;
    } ///calculam a ^ (n-2)
    
    return p;
}

long long getphi(long long nr) {
    long long cur = nr;
    for (long long i = 2; i*i<=nr; i++) {
        if (nr % i == 0) {
            while (nr % i == 0) {
                nr /= i;
            }
            cur = cur * (i-1) / i; ///raman cu i-1/i numere
        }
    }
    if (nr != 1) {
        cur = cur * (nr-1) / nr;
    }
    return cur;
}

int main() {

    fin >> a >> n;
    int exp = getphi(n)-1;
    fout << inversmodular(a, exp, n);
    
    return 0;
}