#include <bits/stdc++.h>

using namespace std;
int a,b;
long long putere(long long a,long long b,int MOD){
    int 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;
}
int phi(int x){
    int rez = x;
    for(int i = 2;i * i <= x;i++){
        if(x % i == 0){
            while(x % i == 0)
                x /= i;
            rez -= rez / i;
        }
    }

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

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