#include <stdio.h>

long long int exp_log(long long int x, int n)
{
    /*if (n < 0)
     {
         x = 1.0 / x;
         n = (-1) * n;
     }
 */
    n = n % 1999999973;

    if (n == 0)
    {
        return 1;
    }
    long long int p = 1;
    while (n > 0)
    {
        if (n % 2)
        {
            p = (p * x) % 1999999973;
        }
        x = (x * x) % 1999999973;
        n = n / 2;
    }
    return p;
}

int main(void)
{
    long long int N, P;
    long long sol;

    FILE *f, *g;

    f = fopen("lgput.in", "w");
    g = fopen("lgput.out", "r");

    fscanf(f, "%lld %lld", &N, &P);

    sol = exp_log(N, P);

    fprintf(g, "%lld", sol);

    return 0;
}