//
//  main.c
//  ridicare_putere_log
//
//  Created by Bran Eduard Denis on 30.05.2023.
//

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

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

int main() {
    long long int N;
    long long int P;
    FILE*f;
    f=fopen("lgput.in","rt");
    fscanf(f,"%lld %lld",&N,&P);
    f=fopen("lgput.out","wt");
    fprintf(f,"%lld",putere(N,P));
    fclose(f);
    return 0;
}