#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;
}
int cmmdc(LL a, LL b)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
long long int puteri(LL N)
{
    int n = 0; // nr de numere prime
    for (LL i = 1; i < N; i++)
    {
        if(cmmdc(i,N)==1)
        {
            n++;
        }
    }
    return n-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;
}