#include <fstream>
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()
{
    int i,j,a,n,n1;
    char v[2000000];
    fin>>a>>n;
    n1=n;
    for(i=2;i<=n;++i)
    {
       if(!v[i])
       {
           if(n%i==0)
           {
           n=n*(i-1)/i;
           }
           for(j=2*i;j<=n;j+=i)
           {
               v[j]='1';
           }
       }
    }
    fout<<rid_put(a,n-1)%n1;

}