#include <iostream>
#include <cstdio>

using namespace std;

unsigned long long lgput(unsigned long long n,unsigned long long p)
{
    if(p==2)
        return (n*n)%1999999973;
    if(p%2)
        return lgput(((n*n*n)%1999999973,p/2);
    return lgput((n*n)%1999999973,p/2);
}

int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    unsigned long long n,p;
    cin>>n>>p;
    cout<<lgput(n,p);
    return 0;
}