#include <iostream>
#include <fstream>

#define int long long

using namespace std;

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

int lgpow(int base, int pow, int mod){
    if(pow == 0) return 1;
    int gratziela;
    pow % 2 == 0 ? gratziela = 1 : gratziela = base;
    return (((lgpow(base, pow / 2, mod) * lgpow(base, pow / 2, mod)) % mod) * gratziela) % mod;
}

int phi(int n){
    int ans = n;
    for(int div = 2; div * div <= n; div++){
        if(n % div == 0){
            ans = ans * (div - 1) / div;
            while(n % div == 0) n /= div;
        }
    }
    if(n > 1) ans = ans * (n - 1) / n;
    return ans;
}

signed main(){
    int a, n;
    fin >> a >> n;
    fout << lgpow(a, phi(n) - 1, n);
    return 0;
}