#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll N, K;

ll phi(ll n) {
    float result = n;

    for (ll p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            result *= (1.0 - (1.0 / (float)p));
        }
    }

    if (n > 1)
        result *= (1.0 - (1.0 / (float)n));

    return (int)result;
}

int main(){

    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%lld%lld", &N, &K);

    ll put = phi(K) - 1;
    ll nr = N;
    ll crt = 1;

    for(ll p = 1; p <= put; p <<= 1){
        if (p & put)
            crt = (crt * nr) % K;
        nr = nr * nr % K;
    }

    printf("%lld", crt);

    return 0;
}