/*#include <cstdio>
long long n, x;
int mod=1999999973;
void citire()
{
    scanf("%lld%lld", &n, &x);
}
int ridp(long long n, long long x)
{
    int nr=0;
    if(x==0)
        return 1;
    if(x%2==0)
    {
        nr=ridp(n,x/2)%mod;
        return ((nr%mod)*(nr%mod))%mod;
    }
    else
    {
        return ((ridp(n, x-1)%mod)*(n%mod))%mod;
    }
}
void rezolva_problema()
{
    long long p=0;
    citire();
    p=ridp(n,x)%mod;
    printf("%lld\n", p);
}
int main()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    rezolva_problema();
    return 0;
}
*/
#include <stdio.h>
#include <string.h>

const int n_max = 10001; // Definim numarul maxim de cifre al numerelor
const int m = 1999999973;

int main()
{
    unsigned int i, n, p;
    long long a, sol = 1;

    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%d %d", &n, &p);
    a = n;
    for (i = 0; (1<<i) <= p; ++ i)  // Luam toti biti lui p la rand
    {
        if ( ((1<<i) & p) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
            sol= (sol * a) % m;

            a=(a * a) % m; // Inmultim a cu a ca sa obtinem n^(2^(i+1))
    }
    printf("%lld\n", sol); // Afisam solutia
}