#include <stdio.h>

#define MOD 1999999973  // modulul dat in problema, il punem define ca sa nu scriem numarul de 10 ori

// am luat varianta iterativa din curs si am adaptat-o pentru long long si modular

long long exp_log(long long x, long long n)
{
    if (n == 0)   // orice numar la puterea 0 e 1
        return 1;

    x = x % MOD; // reducem baza de la inceput ca sa nu avem overflow la inmultiri, sa zicem ca daca avem x=10^10 atunci il reducem la 7

    long long p = 1; // p = rezultatul, incepem de la 1 

    while (n > 0)
    {
        if (n % 2 == 1)         // daca bitul curent e 1 (n e impar), ca in curs
        {
            p = p * x % MOD;    // mai inmultim rezultatul cu x, sa nu avem din nou overflow
        }

        x = x * x % MOD;       // ridicam la patrat x la fiecare pas si din nou facem % MOD pt a nu avea overflow
        n = n / 2;              // trecem la urmatorul bit
    }

    return p;
}

int main()
{
    FILE *fin  = fopen("lgput.in.txt",  "r");
    FILE *fout = fopen("lgput.out.txt", "w");

    if (fin == NULL) // verificam daca s-a deschis fisierul
    {
        printf("Eroare la deschiderea fisierului\n");
        return 1;
    }

    long long n, p; // folosim long long pentru ca valorile pot fi pana la 2^32
    fscanf(fin, "%lld %lld", &n, &p); 

    long long rezultat = exp_log(n, p);

    fprintf(fout, "%lld\n", rezultat);

    fclose(fin);
    fclose(fout);

    return 0;
}