#include<iostream>
using namespace std;

unsigned long int n;
unsigned long int p;
unsigned long int nr = 1;

void inmultire(void)
{
     for(unsigned long int i=1;i<=p;i++)
        nr = (nr*n)%9000000000;
}

void citire(void)
{
     FILE *f = fopen("lgput.in","r");
     
     fscanf(f,"%d %d",&n,&p);
     
     fclose(f);
}

int main()
{
    FILE *f = fopen("lgput.out","w");
    
    citire();
    inmultire();
    fprintf(f,"%d",nr%1999999973);
    
    fclose(f);
}