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

long long Ridicare_la_putere_in_timp_logaritmic(FILE *fis,FILE *gis)
{
    int n=0,p=0;
    long long sol=1;
    const long MO=1999999973;
    fscanf(fis,"%d",&n);//citim datele din fisier
    fscanf(fis,"%d",&p);//n e numarul,p e exponentul puterii
    while(p!=0)//am folosit algorimtul din curs iterativ pentru a avea o complexitate O(log p)
    {
        if(p%2==1)
        {
            sol=(sol*n)%MO;
        }
        n=(n*n)%MO;//actualizam baza
        p=(p/2)%MO;
    }
    return (sol%MO);//returnam solutia problemei
}
int main(void)
{   
    FILE *fis=NULL,*gis=NULL;//fisiere
    fis=fopen("lgput.in","r");//deschidem fisiere
    if(fis==NULL)
    {
        perror("eroare la deschiderea fisierului de intrare\n");
        exit(-1);
    }
    gis=fopen("lgput.out","w");
    if(gis==NULL)
    {
        perror("eroare la deschiderea fisierului de iesire\n");
        exit(-1);
    }
    fprintf(gis,"%lld\n",Ridicare_la_putere_in_timp_logaritmic(fis,gis));//rezolvarea
    fclose(fis);//inchidem fisiere
    fclose(gis);

    return 0;
}