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

#define mod 1999999973

FILE *f = NULL;

int n, p;
int baza[3][3], sol[3][3];

void inmult_matr(int a[3][3], int b[3][3])
{
    long long int c[3][3];
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            c[i][j] = 0;
        }
    }
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                c[i][j] = (c[i][j] + (long long)(a[i][k] * b[k][j])) % mod;
            }
        }
    }
    for(int  i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            a[i][j] = c[i][j];
        }
    }
}

void lgput()
{
    sol[0][0] = sol[1][1] = 1;
    baza[0][0] = n;
    baza[1][1] = 1;
    
    while(p)
    {
        if(p%2)
        {
            inmult_matr(sol, baza);
        }
        inmult_matr(baza, baza);
        p = p / 2;
    }
    if((f = fopen("lgput.out", "w")) == NULL)
    {
        exit(-1);
    }
    fprintf(f, "%d", sol[0][0]%mod);
    fclose(f);
}

int main(void)
{
    if((f = fopen("lgput.in", "r")) == NULL)
    {
        exit(-1);
    }
    fscanf(f, "%d %d", &n, &p);
    fclose(f);
    lgput();
    return 0;
}