#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

long long exp(long long x, long long n){
    cout<<x<<endl;
    if(n==0) return 1;
    if(n%2==0) return (exp((x*x)%1999999973, n/2))%1999999973;
    else return (x*exp((x*x)%1999999973,(n-1)/2))%1999999973;
}

int main()
{
    long x, n;
    fin>>x>>n;
    fout<<exp(x,n);
    return 0;
}