#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 n){
     long long d = 2, p, prod = n;
    while ( d * d <= n ) {
        p = 0;
        while ( n % d == 0 ) {
            n /= d;
            p ++;
        }
        if ( p )
            prod = prod / d * ( d - 1 );
        d ++;
    }
    if ( n > 1 )
        prod = prod / n * ( n - 1 );
    return prod;
}
int main()
{

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