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

#include <iostream>
#include <fstream>
#define m 1999999973

using namespace std;
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_biti/Ridicare la putere in timp logaritmic_biti/lgput.in");
    ofstream g("lgput.out");
    long long n,p,i,rez=1;
    f>>n>>p;
    long long a=n;
    for(i=0;(1<<i)<=p;i++){
        if(((1<<i)&p)>0)
            rez*=a%m;
        a*=a%m;
    }
    g<<rez;
    return 0;
}