#include <bits/stdc++.h>
using namespace std;

ifstream f("lgput.in");
ofstream g("lgput.out");

const long long MOD = 1999999973;
long long n, p;

inline void solve()
{
    long long ans = 1, x = p, pi = p;
    while(p--)
    {
        if(n%2==1)
            ans*=x%MOD;
        x*=pi;
        n>>=1;
        ans%=MOD;
    }
    g << ans%MOD;
}

int main()
{
    f >> n >> p;
    solve();
}