#include <stdio.h>

FILE *fin = NULL, *fout = NULL;
long long mod;
long long phi(long long n)
{
    long long rezultat = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
                n = n / i;
            rezultat = rezultat - rezultat / i;
        }
    }
    if (n > 1)
        rezultat = rezultat - rezultat / n;
    return rezultat;
}

long long ridicare(long long a, long long n)
{
    long long rezultat = 1;
    while (n > 0)
    {
        if (n % 2 == 1)
            rezultat = (rezultat * a)%mod;
        a = (a * a)%mod;
        n = n / 2;
    }
    return rezultat;
}

int main()
{
    long long a,n;
    fin = fopen("inversmodular.in", "r");
    fout = fopen("inversmodular.out", "w");
    fscanf(fin, "%lld %lld", &a, &n);
    mod = n;
    fprintf(fout, "%lld", ridicare(a, phi(n)-1));
    fclose(fin);
    fclose(fout);
    return 0;
}