#include <fstream>

std :: ifstream fin("lgput.in");
std :: ofstream fout("lgput.out");

const int MOD = 1999999973;
unsigned long long ridicare_la_putere(unsigned long long x, unsigned long long n)
{
    if (n == 0)
        return 1;

    unsigned long long result;

    if (n & 1)
    {
        result = ridicare_la_putere(x % MOD, (n - 1) / 2) % MOD;
        return ((x % MOD) * result * result) % MOD;
    }

    result = ridicare_la_putere(x % MOD, n / 2) % MOD;

    return (result * result) % MOD;
}

int main() {
    unsigned long long x, n;
    // fin >> x >> n;
    cout << ridicare_la_putere(4, 6);
    return 0;
}