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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ifstream fin("lgput.in");
    ofstream fout("lgput.out");

    int n,p;
    fin>>n>>p;
    int progress = 0;
    const ll m = 1999999973;

    map<ll,ll> toPow(p+1,0);

    toPow[0] = 1;
    toPow[1] = n%m;
    int cnt;

    for(int i = 2; i <= p; i*=2){
        toPow[i] = (toPow[i/2]*toPow[i/2])%m;
        progress = i;
        cnt = i;
    }





    while(progress < p){
        while(progress+cnt > p){
            cnt/=2;
        }
        toPow[progress+cnt] = (toPow[progress] + toPow[cnt])%m;
        progress += cnt;
    }

    fout<<toPow[p];








    return 0;
}