#include <stdio.h>
#define LL long long
long long int Putere(unsigned int n, unsigned int p, LL M)
{
    unsigned long long res = 1;
    long long int a=1;
    while (p > 0)
    {
        if (p % 2 == 1)
        {
            res = (a * res * n) % M;
        }
        n = (a * n * n) % M;
        p = p / 2;
    }
    return res;
}
long long int puteri(LL N)
{
    LL result = N;
    for (LL 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-1;
}
int main()
{
    LL N = 0;
    LL A = 0;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%lld %lld\n", &A, &N);
    printf("%lld",Putere(A,puteri(N),N));

    return 0;
}