#include <stdio.h>
using namespace std;

int a, n, phi, mod;

int plog(int x, int pw) {
    if(!pw) return 1;
    int aux = plog(x, pw >> 1);
    return ((1LL * aux * aux) % mod * ((pw & 1)?x:1))% mod;
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%d %d", &a, &n);
    phi = mod = n;
    for(int i = 2; 1LL * i * i <= n; i++)
        if(n % i == 0) {
            while(n % i == 0) n /= i;
            phi = phi / i * (i - 1);
        }
    if(n > 1) phi = phi / n * (n - 1);

    printf("%d\n", plog(a, phi - 1));

    return 0;
}