#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;
}

long long int exponentiate(long long int base, int exponent, int mod) {
    if(exponent == 0) {
        return 1;
    }

    if(exponent % 2) {
        return (base * exponentiate((base * base) % mod, (exponent - 1) / 2, mod)) % mod;
    }
    else {
        return (exponentiate((base * base) % mod, exponent / 2, mod)) % mod;
    }
}

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

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

    int result = exponentiate((long long int)a, phi(n) - 1, n);
    fprintf(fileOut, "%lld\n", result);

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