#include <iostream>
#include <stdio.h>

#define MODULO 1999999973

using namespace std;

FILE *f = fopen( "lgput.in", "r" );
FILE *g = fopen( "lgput.out", "w" );

long putere( int x, int n )
{
    if( n == 0 )
    {
        return 1;
    }
    if( n == 1 )
    {
        return x % MODULO;
    }
    if( n%2 == 0 )
    {
        return putere( x*x, n/2 ) % MODULO;
    }
    else
    {
        return x * putere( x*x, (n-1)/2 ) % MODULO;
    }
}

int main()
{
    long n, p;
    fscanf( f, "%ld %ld", &n, &p );

    fprintf( g, "%ld", putere( n, p ) );

    fclose( f );
    fclose( g );
    return 0;
}