pavare2

#include <iostream>
#define KMAX 30
#define MOD 1000000007
int k,n;
int64_t dp[KMAX]={1,1,2,4};
struct Matrix
{
    int64_t mat[KMAX][KMAX]={};
    inline int64_t* operator[](int ind)
    {
        return mat[ind];
	}
};

Matrix nullMat;
Matrix initMat;

Matrix operator*(Matrix a,Matrix b)
{
    Matrix prod;
    for(int i=0;i<k;++i)
        for(int j=0;j<k;++j)
            for(int l=0;l<k;++l)
                prod[i][j]=(prod[i][j]+a[i][l]*b[l][j]%MOD)%MOD;
    return prod;
}

Matrix pow(Matrix mat,int n)
{
    if(!n)
        return nullMat;
    if(n&1)
        return mat*pow(mat*mat,n>>1);
    return pow(mat*mat,n>>1);
}

int main()
{
    std::cin>>k>>n;
    for(int i=0;i<(k>3?k:3);++i)
        nullMat[i][i]=1;
    if (k==1)
    {
        if(n==1) {std::cout<<"1\n";return 0;}
        if(n==2) {std::cout<<"2\n";return 0;}
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        k=3;
        initMat[0][0]=1;
        initMat[1][0]=1;
        initMat[2][0]=1;
        initMat[0][1]=1;
        initMat[1][2]=1;
        int64_t sol=0;
        Matrix pwr=pow(initMat,n-2);
        for(int i=0;i<k;++i)
            sol=(sol+dp[k-i-1]*pwr[i][0]%MOD)%MOD;
        std::cout<<sol<<'\n';
        return 0;
    }
    if (k==2)
    {
        if(n==2)
        {
            std::cout<<"3\n";
            return 0;
        }
        dp[0]=1;
        dp[1]=1;
        dp[2]=3;
        k=3;
        initMat[0][0]=1;
        initMat[1][0]=2;
        initMat[2][0]=1;
        initMat[0][1]=1;
        initMat[1][2]=1;
        int64_t sol=0;
        Matrix pwr=pow(initMat,n-2);
        for(int i=0;i<k;++i)
            sol=(sol+dp[k-i-1]*pwr[i][0]%MOD)%MOD;
        std::cout<<sol<<'\n';
        return 0;
    }
    for(int i=4;i<=k;++i)
        dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%MOD;
    for(int i=1;i<k;++i)
        initMat[i-1][i]=1;
    initMat[0][0]=1;
    initMat[1][0]=1;
    initMat[2][0]=1;
    initMat[k-1][0]=dp[k];
    int64_t sol=0;
    Matrix pwr=pow(initMat,n-k+1);
    for(int i=0;i<k;++i)
        sol=(sol+dp[k-i-1]*pwr[i][0]%MOD)%MOD;
    std::cout<<sol<<'\n';
    return 0;
}