//
//  main.cpp
//  Ridicare la putere in timp logaritmic
//
//  Created by Alex Petrache on 07.09.2015.
//  Copyright (c) 2015 Alex Petrache. All rights reserved.
//

#include <iostream>
#include <fstream>
#define modulo 1999999973
using namespace std;

long long lgput(long long n, long long p){
    if(p==0)
        return 1;
    if(p==1)
        return n;
    if(p%2==0)
        return lgput((n*n)%modulo,p/2)%modulo;
    else
        return (n*lgput((n*n)%modulo,(p-1)/2))%modulo;
}

int main(int argc, const char * argv[]) {
    ifstream f("lgput.in");
//    ifstream f("/Users/alexpetrache/Documents/Programare/Xcode/Arhiva Educationala/Ridicare la putere in timp logaritmic/Ridicare la putere in timp logaritmic/lgput.in");
    ofstream g("lgput.out");
    long long n,p;
    f>>n>>p;
    
    g<<lgput(n,p);
    return 0;
}