CHESGAME - Editorial

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define x first
#define y second
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI (atan(1)*4)
#define mp make_pair
using namespace std;

const ll mod = 1e9 + 7;
#define matrix_mod mod
template<class mat_type>
struct matrix {

    int n_rows, n_cols;
    vector< vector<mat_type> > m;

    matrix(int r = 1, int c = 1, bool I = false) {
        m.resize(r);
        for (int i = 0; i < r; i++) m[i].resize(c, 0);
        n_rows = r;
        n_cols = c;
        if (I)
            make_identity();
    }

    void make_identity() {
        for (int i = 0; i < n_rows; i++) m[i][i] = 1;
    }

#ifndef matrix_mod

    mat_type add(mat_type a, mat_type b) {
        return a + b;
    }

    mat_type sub(mat_type a, mat_type b) {
        return a - b;
    }

    mat_type mul(mat_type a, mat_type b) {
        return a * b;
    }

#else

    mat_type add(mat_type a, mat_type b) {
        return (a + b) % matrix_mod;
    }

    mat_type sub(mat_type a, mat_type b) {
        return ((a - b) % matrix_mod + matrix_mod) % matrix_mod;
    }

    mat_type mul(mat_type a, mat_type b) {
        return (a * b) % matrix_mod;
    }

#endif

    matrix operator +(const matrix& other) {
        matrix ans(n_rows, n_cols);
        for (int i = 0; i < n_rows; i++)
            for (int j = 0; j < n_cols; j++)
                ans.m[i][j] = add(m[i][j], other.m[i][j]);
        return ans;
    }

    matrix operator -(const matrix& other) {
        matrix ans(n_rows, n_cols);
        for (int i = 0; i < n_rows; i++)
            for (int j = 0; j < n_cols; j++)
                ans.m[i][j] = sub(m[i][j], other.m[i][j]);
        return ans;
    }

    matrix operator *(const matrix& other) {
        matrix ans(n_rows, other.n_cols);
        for (int i = 0; i < n_rows; i++)
            for (int j = 0; j < other.n_cols; j++)
                for (int k = 0; k < n_cols; k++)
                    ans.m[i][j] = add(ans.m[i][j], mul(m[i][k], other.m[k][j]));
        return ans;
    }

    matrix power(ll exp) {
        matrix ans(n_rows, n_cols, true);
        matrix multiplier = *this;
        while (exp > 0) {
            if (exp & 1)
                ans = ans * multiplier;
            exp >>= 1;
            multiplier = multiplier * multiplier;
        }
        return ans;
    }
};


void solve() {
    ll n, m;
    cin >> n >> m;
    matrix<ll> init(2 * m, 1);
    matrix<ll> coeff(2 * m, 2 * m);
    init.m[0][0] = 1;
    for (int i = m; i < (2 * m); i++) {
        coeff.m[i][i - m] = 1;
    }
    for (int i = 0; i < m; i++) {
        if (i >= 2)
            coeff.m[i][i - 2] = 1;
        if ((i + 2) < m)
            coeff.m[i][i + 2] = 1;
        if (i >= 1)
            coeff.m[i][i - 1 + m] = 1;
        if ((i + 1) < m)
            coeff.m[i][i + 1 + m] = 1;
    }
    coeff = coeff.power(n);
    coeff = coeff * init;
    cout << coeff.m[2 * m - 1][0];
}
int main()
{
    fastread;
    solve();
    return 0;
}