#include <fstream>
#include <math.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout ("inversmodular.out");
const int mod=1999999973;
int rid_put(long long a,long long n)
{
    int p=1;
    for(long long i=1;i<=n;i<<=1)
    {
        if(n&i) p=(1LL*p*a)%mod;
        a=(1LL*a*a)%mod;
    }
    return p;
}
int main()
{
    long long i,j,a,n,n1,n2;
    char v[2000000];
    fin>>a>>n;
    n1=n;
    n2=n;
    for(i=2;i<=sqrt(n2);++i)
    {
        if(n%i==0)
        {
        while(n%i==0)
        {
            n/=i;
        }
        n1=n1*(i-1)/i;
        }
    }
    if(n!=1)
    {
        n1=n1*(n-1)/n;
    }
    fout<<rid_put(a,n1-1)%n2;

}