#include <stdio.h>

long long findTotient(long long n) {
    long long result = n;

    for(long long i=2;i*i<=n;i++) {
        if(n % i == 0) {
            while(n % i == 0) {
                n /= i;
            }
            result = (result / i) * (i - 1);
        }
    }

    if(n > 1) {
        result = (result / n) * (n - 1);
    }

    return result;
}


long long modularExp(long long base, long long exp, long long mod) {
    if(mod == 0) {
        return -1;
    }
    
    long long result = 1;
    base = base % mod;

    while(exp > 0) {
        if(exp % 2 == 1) {
            result = (result * base) % mod;
        }

        base = (base * base) % mod;
        exp /= 2;
    }

    return result;
}


int main() {
    FILE *input, *output;

    input = fopen("inversmodular.in", "r");
    output = fopen("inversmodular.out", "w");

    long long a, n;

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

    long long phi = findTotient(n);

    long long inv = modularExp(a, phi-1, n);

    fprintf(output, "%lld", inv);

    fclose(input);
    fclose(output);


    // long long power = findTotient(n)-1;
    // long long number = a;
    // long long result = 1;


    //LL put = getphi(M) - 1;
	//LL nr = N;
	// LL crt = 1;
    // for(LL p = 1;p <= put;p <<= 1)
    // {
	//  	if (p & put) crt = (crt * nr) % M;
	//   	nr = (nr * nr) % M;
	// }

    return 0;
}