【題目敘述】https://cses.fi/problemset/task/1096
#include <iostream>
using namespace std;
long long n, a[6][6], ans[6], mod = 1e9+7;
int main() {
cin >> n;
for (int i = 0; i < 5; i++){
a[i][i+1] = 1;
}
for (int i = 0; i < 6; i++){
a[5][i] = 1;
}
ans[5] = 1;
while (n){
if (n & 1){
long long tmp[6] = {};
for (int i = 0; i < 6; i++){
for (int j = 0; j < 6; j++){
tmp[i] += a[i][j]*ans[j];
tmp[i] %= mod;
}
}
for (int i = 0; i < 6; i++){
ans[i] = tmp[i];
}
}
long long tmp[6][6] = {};
for (int i = 0; i < 6; i++){
for (int j = 0; j < 6; j++){
for (int k = 0; k < 6; k++){
tmp[i][j] += a[i][k]*a[k][j];
tmp[i][j] %= mod;
}
}
}
for (int i = 0; i < 6; i++){
for (int j = 0; j < 6; j++){
a[i][j] = tmp[i][j];
}
}
n >>= 1;
}
cout << ans[5] << "\n";
}