#include <iostream>
#include <fstream>

std::ifstream f ("lgput.in");
std::ofstream g ("lgput.out");

#define M 1999999973

using namespace std;

/// x is the number to be raised at the n-th power
long long x, n;

void exponentiate(int x, int n) {
    long long   result = 1;
    long long   mask_length = 0;
    long long   mask = 0;

    /// Count the number of bits the mask has
    mask = n;
    while (mask != 0) {
        mask = mask >> 1;
        mask_length += 1;
    }
    /// Build the mask
    mask = 1 << (mask_length - 1);

//    cerr << result << " ";

    /// Repeat until the last bit of "n" is procesed
    while (mask != 0) {
        /// If the current bit of "n" is 1:

        if (mask & n) {
            result = ((result%M) * (result%M) * (x%M));
            cerr << "1 ";
            cerr << result << "\n";
        } else {
            /// result*result can't be greater than the maximum of long long
            cerr << "2 ";
            cerr << result << "\n";
            result = ((result%M)*(result%M))%M;
        }
        /// Shift the mask one bit to the right
        mask = mask >> 1;
    }

    g << result;
}

int main()
{
    /// Read x and n
    f >> x >> n;
    /// Call the function that raises x to the n-th power (mod m)
    exponentiate(x, n);
    return 0;
}