#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#define mod 1999999973

const int n_max=10001; 

int main(void)
{
	unsigned int i,n,p;
	long long aux, rezultat=1;

	FILE *fin=fopen("lgput.in","r");
	FILE *fout=fopen("lgput.out","w");
    
    if(fin==NULL)//verificam deschiderile celor 2 fisiere
    {
        perror("Eroare la deschiderea fisierului de citire.\n");
        exit(1);
    }
    if(fout==NULL)
    {
        perror("Eroare la deschiderea fisierului de scriere.\n");
        exit(1);
    }
    
	if(fscanf(fin,"%d %d", &n, &p)!=2)//citim cele 2 numere n si puterea
	{
	    perror("Eroare la citirea din fisier.\n");
        exit(1);
	}
	
    aux=n;
	for (i=0;(1<<i)<=p;++i)//complexitate O(logN)
	{
		if (((1<<i)&p)>0)//verificam daca bitul i din p e 1
			{
			  rezultat=(rezultat*aux)%mod;//se adaugă in rezultat contributia bazei curente daca bitul i e 1
			}
			aux=(aux*aux)%mod; 
	}
    
	fprintf(fout,"%lld\n",rezultat);
	
	if(fclose(fin)!=0)//verificam si inchiderile
    {
        perror("Eroare la inchiderea fisierului de citire.\n");
        exit(1);
    }

    if(fclose(fout)!=0)
    {
        perror("Eroare la inchiderea fisierului de scriere.\n");
        exit(1);
    }
    return 0;
}