#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 += 2) {
        int exp = 0;
        while(n % i == 0) {
            n /= i;
            exp++;
        }
        
        if(exp > 0) {
            rez = rez / i * (i - 1);
        }

        if(i == 2) {
            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;
}