#include <bits/stdc++.h>

using namespace std;

vector <int> nr_prime;

const int MOD=1999999973;

void descomp_prim(int n)
{
    int d=2;
    while(n!=1)
    {
        if(n%d==0)
        {
            nr_prime.push_back(d);
            while(n%d==0)
                n/=d;
        }
        d++;
    }
}

int putere(int n)
{
    int k=nr_prime.size();
    if(k==1)
        return n-1;
    for(int i=0;i<nr_prime.size();i++)
        k=k*(nr_prime[i]-1)/nr_prime[i];
    return k;
}


int multy(int& a, int b)
{
    a=int64_t(a)*b%MOD;
}

int exp_by_squaring(int a, int b)
{
    int ans = 1;
    while (b > 0)
    {
        if (b&1)
            multy(ans, a);
        b>>=1;
        multy(a, a);
    }
    return ans;
}

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

    scanf("%d%d", &a, &n);
    descomp_prim(n);
    int phi_n=putere(n);
    printf("%d\n", exp_by_squaring(a, phi_n-1)%n);

    return 0;
}