#include <iostream>
#include <fstream>

#define Max 1999999973;

using namespace std;


int main()
{
    unsigned int i, n, p;
    long long a, sol = 1;

    ifstream f("lgput.in");
    ofstream g("lgput.out");
    f>>n>>p;
    n=2,p=3;
    a = n;

    for (i = 0; (1<<i) <= p; i++)
    {
        if (( (1<<i) & p) > 0)
            sol= (sol * a) % Max;
            a=(a * a) % Max;
    }
    g<<sol;
}
/**

n=2 p=3
a=2

i=0   0001 < 3 ->true
{
    0001 & 0011 >0 -> true
    sol = 2
    a= 4
}
i=1   0010 < 3 ->true
{
    0010 & 0011 >0 -> true
    sol = 8
}
i=2   0100 < 3 ->false
{
    0001 & 0011 >0 -> true
    sol = 2
}

**/