#include<bits/stdc++.h>
using namespace std;
long long n,a,k=1999999973;
long long put(long long n, long long a){
	if(n==0)return 1;
	if(n==1)return a;
	else
	if(n%2==0)return put(n/2,a*a);
	else
	return put(n/2,(a*a)%k)*a;
}
int main(){
	ifstream cin("lgput.in");
	ofstream cout("lgput.out");
	cin>>n;
	cin>>a;
	cout<<put(n,a);
	return 0;
}