#include<stdio.h>

long long phi(long long num) {
    long long rez = num;
    for (long long i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            while (num % i == 0) { // scapam de toti multiplii lui 'i' in 'num'
                num /= i;
            }
            rez -= rez/i; //  (rez/i) == este numarul de multipli lui "i" pe care le are "n"
        }
    }
    if (num > 1) {
        rez--; //aceasta se activeaza cand num este prim, atunci numarul de numere mai mici si prime cu num este 'num' fara elementul 1, deatata -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 = phi(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;
}