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

void citire(int *N, int *P)
{
    int n,p;
    FILE *f;
    if((f=fopen("lgput.in", "r"))==NULL)
    {
        perror("eroare deschidere fisier\n");
        exit(1);
    }
    if(fscanf(f,"%d %d", &n, &p)!=2)
    {
        exit(1);
    }
    fclose(f);
    *N=n;
    *P=p;
}

void afisare(int exp)
{
    FILE *g;
    if((g=fopen("lgput.out", "w"))==NULL)
    {
        perror("eroare deschidere fisier2\n");
        exit(1);
    }
    fprintf(g, "%d", exp);
    fclose(g);
}

int exp_log(int N, int P, int mod)
{
    int exp=1;
    if (P<0)
    {
        N=1.0/N;
        P=(-1)*P;
    }
    else if (P==0)
    {
        return 1;
    }
    else
    {
        while (P>0)
        {
            if(P%2==1)
            {
                exp=exp*N%mod;
            }
            N=N*N%mod;
            P=P/2;
        }
    }
    return exp;
}

int main()
{
    int N, P, mod=1999999973;
    citire(&N,&P);
    int exp=exp_log(N, P, mod);
    afisare(exp);
    return 0;
}