#include <stdio.h>
#include <string.h>


long long inmultireLog(long long n, long long p, long long MOD) {
    long long rez = 1;

    n %= MOD;
    while(p) {
        if(p % 2 == 1) {
            rez = (rez * n);
        }
        n *= n;
        n %= MOD;
        p /= 2;
    }

    return rez;
}

int phi(int n) {
    int rez = n;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            while(n % i == 0) {
                n /= i;
            }
            rez -= rez / i;
        }
    }
    if(n > 1) {
        rez -= rez / n;
    }
    
    return rez;
}


int main() {
    FILE *input = fopen("inversmodular.in", "r");
    FILE *output = fopen("inversmodular.out", "w");

    long long a, n;
    fscanf(input, "%lld %lld", &a, &n);

    printf("phi(n) = %d", phi(n));
    fprintf(output, "%lld", inmultireLog(a, phi(n) - 1, n) % n);
    
    fclose(input);
    fclose(output);

    return 0;
}