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

#define MAGIC_NUMBER 1999999973

using namespace std;

int main()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);

    long long base, exponent;

    scanf("%lld %lld", &base, &exponent);

    long long result = 1;

    while (exponent != 0){

        if (exponent %2 == 1) {
            result = result * base % MAGIC_NUMBER;
        }

        base = base*base % MAGIC_NUMBER;
        exponent /= 2;
    }

    printf("%lld", result);

    return 0;
}