#include <stdio.h>
#include <stdlib.h>

#define FILE_IN "inversmodular.in"
#define FILE_OUT "inversmodular.out"

int a, n;

int gcd(int a, int b) {
    while(b) {
        int aux = b;
        b = a % b;
        a = aux;
    }

    return a;
}

int totient(int n) {
    int count = 0;
    for(int i = 1; i < n; i++) {
        if(gcd(i, n) == 1) count++;
    }
    return count;
}

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

int exponentiate(int x, int n, int MOD) {
    if(n == 0) {
        return 1;
    }

    if(n % 2 == 1) {
        return (x * exponentiate((x * x) % MOD, (n - 1) / 2, MOD)) % MOD;
    }
    else {
        return (exponentiate((x * x) % MOD, n / 2, MOD)) % MOD;
    }
}

int main()
{
    FILE *fileIn = fopen(FILE_IN, "r"),
         *fileOut = fopen(FILE_OUT, "w");

    fscanf(fileIn, "%d%d", &a, &n);

    fprintf(fileOut, "%d\n", exponentiate(a, phi(n) - 1, n));

    fclose(fileIn);
    fclose(fileOut);
    return 0;
}