Sol
直接矩阵快速幂
推出来的矩阵应该长这样
\begin{equation*} \begin{bmatrix} 1&1&1&1&1&1\\ 1 & 0&0&0&0&0\\ 0 & 0&1&3&3&1\\ 0 & 0&0&1&2&1\\ 0 & 0&0&0&1&1\\ 0 & 0&0&0&0&1\\ \end{bmatrix}^{i - 1}* \begin{bmatrix} F_{1}\\ F_0\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}= \begin{bmatrix} 1&1&1&1&1&1\\ 1 & 0&0&0&0&0\\ 0 & 0&1&3&3&1\\ 0 & 0&0&1&2&1\\ 0 & 0&0&0&1&1\\ 0 & 0&0&0&0&1\\ \end{bmatrix}* \begin{bmatrix} F_{i - 1}\\ F_{i - 2}\\ i^3\\ i^2\\ i\\ 1 \end{bmatrix}= \begin{bmatrix} F_{i}\\ F_{i - 1}\\ (i + 1)^3\\ (i + 1)^2\\ i + 1\\ 1 \end{bmatrix} \end{equation*}
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long
//#define int long long
using namespace std;
const int mod = 1e9 + 7;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int T;
LL N;
struct Matrix {
LL a[10][10], N;
Matrix() {
N = 6;
memset(a, 0, sizeof(a));
}
Matrix operator * (const Matrix &rhs) const {
Matrix ans;
for(int k = 1; k <= N; k++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
(ans.a[i][j] += (1ll * a[i][k] * rhs.a[k][j]) % mod) %= mod;
return ans;
}
};
Matrix fp(Matrix a, LL p) {
Matrix base;
// printf("%d", base.a[0][1]);
for(int i = 1; i <= 6; i++) base.a[i][i] = 1;
while(p) {
if(p & 1) base = base * a;
a = a * a; p >>= 1;
}
return base;
}
const LL GG[10][10] = {
{0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1},
{0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 3, 3, 1},
{0, 0, 0, 0, 1, 2, 1},
{0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 1}
};
int main() {
T = read();
while(T--) {
N = read();
if(N == 1) {puts("1"); continue;}
if(N == 2) {puts("16"); continue;}
Matrix M;
memcpy(M.a, GG, sizeof(M.a));
Matrix ans = fp(M, N - 2);
LL out = 0;
(out += ans.a[1][1] * 16) %= mod;
(out += ans.a[1][2] * 1) %= mod;
(out += ans.a[1][3] * 27) %= mod;
(out += ans.a[1][4] * 9) %= mod;
(out += ans.a[1][5] * 3) %= mod;
(out += ans.a[1][6]) %= mod;
printf("%lld\n", out % mod);
}
return 0;
}
/*
5
4
1
2
3
100
*/