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

#define mod 1999999973

FILE *fin = NULL;
FILE *fout = 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 = 1; i <= 2; i++)
    {
        for(int j = 1; j <= 2; j++)
        {
            c[i][j] = 0;
        }
    }
    for(int i = 1; i <= 2; i++)
    {
        for(int j = 1; j <= 2; j++)
        {
            for(int k = 1; k <= 2; k++)
            {
                c[i][j] = (c[i][j] + (long long)(a[i][k]) * (long long)(b[k][j])) % mod;
            }
        }
    }
    for(int  i = 1; i <= 2; i++)
    {
        for(int j = 1; j <= 2; j++)
        {
            a[i][j] = c[i][j];
        }
    }
}

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

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