#include <iostream>

using namespace std;

FILE *fin, *fout;

const long long MOD = 1999999973;

int lgput(long base, long exp)
{
    int p = base, p1 = 1;

    while(exp)
    {
        if(exp % 2 == 1)
        {
            p1 = 1LL * p1 * p % MOD;
            exp--;
        }
        else

        {
            p = 1LL * p * p % MOD;
            exp /= 2;
        }
    }

    return p1;
}

int euler(int n)
{
    int euler = n, d = 2;

    while(d * d <= n)
    {
        if(n % d == 0)
        {
            euler = euler / d * (d - 1);

            while(n % d == 0)
                n /= d;
        }

        d++;
    }

    if(n > 1)
        euler = euler / n * (n - 1);

    return euler;
}

int main()
{
    fin = fopen("inversmodular.in", "r");
    fout = fopen("inversmodular.out", "w");

    int a, n;
    fscanf(fin, "%d%d", &a, &n);

    fprintf(fout, "%d", lgput(a , euler(n) - 1) % n);

    fclose(fin);
    fclose(fout);
    return 0;
}