Walker

#include <bits/stdc++.h>
#define M 666013
using namespace std;
unsigned long long n,k;
long long a[3][3],b[3][3],aux[3][3];

void inmulteste1()
{
    for(int i=1;i<=2;++i)
    {
        for(int j=1;j<=2;++j)
        {
            aux[i][j]=0;
            for(int k=1;k<=2;++k)
                aux[i][j]=(aux[i][j]+1LL*b[i][k]*a[k][j])%M;
        }
    }
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            b[i][j]=aux[i][j];
}

void inmulteste2()
{
    for(int i=1;i<=2;++i)
    {
        for(int j=1;j<=2;++j)
        {
            aux[i][j]=0;
            for(int k=1;k<=2;++k)
                aux[i][j]=(aux[i][j]+1LL*a[i][k]*a[k][j])%M;
        }
    }
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            a[i][j]=aux[i][j];
}

void lgpow(long long exponent)
{
    while(exponent)
    {
        if(exponent&1)
            inmulteste1();
        inmulteste2();
        exponent>>=1;
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    a[1][1]=0,a[1][2]=n-1,a[2][1]=1,a[2][2]=n-2;
    b[1][1]=1,b[2][2]=1;
    lgpow(k);
    cout<<b[1][1];
    return 0;
}