ИГРАЛЬНЫЕ КОСТИ (Матрица)

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

long long n;
vector < vector <int> > zero, one;

vector < vector <int> > mult(vector < vector <int> > a, vector < vector <int> > b) {
    vector < vector <int> > ret = a;
    int n = a.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ret[i][j] = 0;
            for (int k = 0; k < n; k++) {
                ret[i][j] = (ret[i][j] + a[i][k] *1ll* b[k][j]) % mod;
            }
        }
    }
    return ret;
}

vector < vector <int> > binpow(vector < vector <int> > a, long long n) {
    if (n == 0) {
        return zero;
    }
    if (n % 2 == 1) {
        vector < vector <int> > b = binpow(a, n - 1);
        return mult(b, a);
    } else {
        vector < vector <int> > b = binpow(a, n / 2);
        return mult(b, b);
    }
}

int main(){
    zero.resize(6);
    one.resize(6);
    one.resize(6);
    for (int i = 0; i < 6; i++) {
        zero[i].resize(6);
        one[i].resize(6);
        for (int j = 0; j < 6; j++) {
            if (i == j)
                zero[i][j] = 1;
            if (i - 1 == j || j == 5) {
                one[i][j] = 1;
            }
        }
    }

    cin >> n;
    vector < vector <int> > ans = binpow(one, n);
    cout << ans[5][5] << endl;
}