#include <cstdio>  
#include <cstring>  

using namespace std;

#define MOD 1999999973
#define FIN "lgput.in"
#define FOUT "lgput.out"

long N, i, p;
long long A, S;
    
    int main()  
    {    
         freopen(FIN, "r", stdin);  
         freopen(FOUT, "w", stdout);  
         
         scanf("%ld %ld", &N, &p);  
         A = N; S = 1;  
         for (i = 0; (1 << i) <= p; ++i) 
         {  
             if ( ((1 << i) & p) > 0) 
                  S = (S * A) % MOD;  
      
             A = (A * A) % MOD; 
         }  
         printf("%lld\n", S); 
    }