#include<iostream.h>
#include<stdio.h>
#define C 1999999973


long long int ridicare(__int64 baza,__int64 exponent)
    {if(exponent%2!=0)  return (baza%C)*ridicare(baza-1,exponent);
    else       {if(!exponent)      
                            return 1;
                else 
                             return ridicare(baza,exponent/2)*ridicare(baza,exponent/2);}
    }
int main()
    {
    long long int baza,exponent;
    freopen("lgput.in","r",stdin);freopen("lgput.out","w",stdout);
    scanf("%lld %lld",&baza,&exponent);
    printf("%lld",ridicare(baza,exponent));
    fclose(stdin);fclose(stdout);
    return 0;
    }