#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("lgput.in");
ofstream fout ("lgput.out");
int i, j, n, s, maxi, k, sf, sff, in, p;

long long int putere(int x)
{
    long long int rez;
    if(x == 1)
        return n;
    if(x%2 == 0)
    {
        rez=putere(x/2);
        return (rez*rez+1999999973)%1999999973;
    }
    if(x%2 == 1)
    {
        rez=putere(x/2);
        return ((rez*rez)*n+1999999973)%1999999973;
    }

}

    int main()
    {
        fin>>n>>p;
        fout<<putere(p);
    }