#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 exponentiate(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);

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

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