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

#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 get(int x, long long n) {
    vector < vector <int> > zero, one;
    zero.resize(x);
    one.resize(x);
    for (int i = 0; i < x; i++) {
        zero[i].resize(x);
        one[i].resize(x);
        for (int j = 0; j < x; j++) {
            if (i == j) zero[i][j] = 1;
            if (i - 1 == j || j == x - 1)
                one[i][j] = 1;
        }
    }
    Zero = zero;
    vector < vector <int> > ans = binpow(one, n);
    return ans[x - 1][x - 1];
}

int main(){

    cin >> n;
    int ans = (get(6, n) - get(5, n)) % mod;
    ans = (ans + mod) % mod;
    cout << ans << endl;
}