#include<stdio.h>

long long calculareFi(long long num) {
    long long rez = num;
    for (long long i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            while (num % i == 0) {
                num /= i;
            }
            rez = (rez / i) * (i - 1);
        }
    }
    if (num > 1) {
        rez = (rez / num) * (num - 1);
    }
    return rez;
}

int main() {
    long long N, M;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld %lld", &N, &M);
    long long putere = calculareFi(M) - 1;
    long long num = N % M;
    long long rez = 1;
    while (putere > 0) {
        if (putere & 1) {
            rez = (rez * num) % M;
        }
        num = (num * num) % M;
        putere >>= 1;
    }
    printf("%lld\n", rez);
    return 0;
}