#include <bits/stdc++.h>

using namespace std;
long long a,b;
long long putere(long long a,long long b,long long MOD){
    long long i;
    long long sol = 1;
    for(i = 0;(1 << i) <= b;i++){
        if((1 << i) & b)
            sol *= a;
        a *= a;
        sol %= MOD;
        a %= MOD;
    }
    return sol;
}
long long phi(long long x){
    long long rez = x;
    for(long long i = 2;i * i <= x;i++){
        if(x % i == 0){
            while(x % i == 0)
                x /= i;
            rez = (rez / i) * (i - 1);
        }
    }

    if(x > 1){
        rez = (rez / x) * (x - 1);
    }
    return rez;
}
int main()
{

    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    cin >> a >> b;
    cout << putere(a,phi(b) - 1,b);
    return 0;
}