#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
ll ceil2(ll a, ll b) {
return (a + b - 1) / b;
}
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define mod 1999999973;
void solve(){
ll n, p;cin>>n>>p;
ll ans=1;
ll cnt=n;
for(int i=0; (1<<i)<=p; i++){
if(p & (1<<i)){
ans=(ans*cnt)%mod;
}
cnt=(cnt*cnt)%mod;
}
cout<<ans;
}
int main(){
freopen("lgput.in", "rt", stdin);
freopen("lgput.out", "wt", stdout);
ios_base::sync_with_stdio(false); cin.tie(NULL);
// ll t;cin>>t;while(t--){solve();cout<<endl;}
solve();
}