/**
Ridicarea la putere in timp logaritmic

  a^b  -> ne bazam pe faptul ca b se poate descompune in suma de puteri ale lui 2.

Ex:
  a^90 -> a^(64+16+8+2) = a^64 * a^16 * a^8 * a^2

de fapt daca il trecem pe 90 in binar, obtzinem cifre de 1 pentu puterile lui 2 care intra
in descompunerea binara a lui 90  (1011010 = 64+16+8+2)

  Pe de alta parte, puterile se obtzin prin patratziri succesive.
  Astfel, pe ex. de mai sus, partatzirile succesive sunt:
   a -> nu participa la produsul final
   a^2 -> participa
   a^4 -> NU participa
   a^8 -> participa
   a^16 -> participa
   a^32 -> NU participa
   a^64 participa.

Algoritmul:
   exponentul b |   restul b%2   | factorul curent | produsul (puterea finala, cea ceruta)
  --------------+----------------+-----------------+-------------------------------------
       90       | 0(nu participa)|      a          |          1
       45       | 1(participa)   |      a^2        |  ->      a^2
       22       | 0(nu participa |      a^4        |          a^2
       11       | 1(participa)   |      a^8        |  ->      a^2 * a^8
        5       | 1(participa)   |      a^16       |  ->      a^2 * a^8 * a^16
        2       | 0(nu participa)|      a^32       |          a^2 * a^8 * a^16
        1       | 1(participa)   |      a^64       |  ->      a^2 * a^8 * a^16 * a^64
                                               deci rez. final=a^(2+8+16+64) = a^90


*/
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    long long n,p,fcrt,rez=1;
    ifstream fin("lgput.in");
    fin>>n>>p;
    fcrt=n;
    while(p)
    {
        if(p%2)rez=rez*fcrt%1999999973;
        p/=2;
        fcrt=fcrt*fcrt%1999999973;
    }
    ofstream fout("lgput.out");
    fout<<rez;
    return 0;
}