#include <fstream>
#include <math.h>
#define M 1999999973

using namespace std;

// basic log pw;
int lgpow(int n, int pw)
{
    if (pw == 0)
        return 1;

    int res = 0, p = 1;
    while (p <= pw) {
        if (p & pw)
            res += n;
        n = n * n;
        p = p * 2;
    }
    return res;
}
int lgpow_mod_m(long long n, long long pw, int m)
{
    long long res = 0, p = 1;
    while (p <= pw) {
        if (p & pw) {
            res += n;
            res %= m;
        }
        n *= n;
        n %= m;
        p <<= 1;
    }
    return res;
}

int main()
{
    ifstream in("lgput.in");
    ofstream out("lgput.out");
    long long n, p;
    in>>n>>p;
    //out<<lgpow(n, p)<<endl;
    out<<lgpow_mod_m(n, p, M)<<endl;
    return 0;
}