爆搜可得答案序列：

$$1,1,2,4,6,9,14,21,31,46,68,100,147,\ldots$$

瞪眼可得公式：

$$A_n=\begin{cases}\lceil 2^{n-2}\rceil,&n\le 4\\2A_{n-1}-A_{n-2}+A_{n-3}-A_{n-4},&n \ge 5\end{cases} $$

实际上这就是 OEIS A038718：

$$A_n=\begin{cases}\lceil 2^{n-2}\rceil,&n\le 4\\2A_{n-1}+A_{n-3}+1,&n \ge 5\end{cases} $$

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
struct Square
{
	int n, m;
	long long a[5][5];
};
Square operator*(Square a, Square b)
{
	if (a.m != b.n) exit(-1);
	int n = a.n, m = a.m, k = b.m;
	Square c;
	c.n = n, c.m = k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			c.a[i][j] = 0;
	for (int i = 1; i <= n; i++)
		for(int j = 1; j <= k; j++)
			for (int l = 1; l <= m; l++)
				c.a[i][j] += a.a[i][l] * b.a[l][j], c.a[i][j] %= P;
	return c;
}
Square operator^(Square a, long long b)
{
	int n = a.n;
	if (a.n != a.m) exit(-1);
	Square tmp[64];
	tmp[0] = a;
	for (int i = 1; i <= 63; i++)
		tmp[i] = tmp[i - 1] * tmp[i - 1];
	Square c;
	c.n = c.m = n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c.a[i][j] = (i == j);
	for (long long i = 0, j = 1; i <= 63; i++, j <<= 1)
		if (b & j) c = c * tmp[i];
	return c;
}
string s1 =
R"(
4 4
2 1000000006 1 1000000006
1 0 0 0
0 1 0 0
0 0 1 0
)";
string s2 =
R"(
4 1
4
2
1
1
)";
int main()
{
    long long n;
    cin >> n;
    stringstream ss;
    ss << s1 << s2;
    Square p, q;
    ss >> p.n >> p.m;
    for (int i = 1; i <= p.n; i++)
    	for (int j = 1; j <= p.m; j++)
    		ss >> p.a[i][j];
    ss >> q.n >> q.m;
    for (int i = 1; i <= q.n; i++)
    	for (int j = 1; j <= q.m; j++)
    		ss >> q.a[i][j];
    if (n <= 4)
    {
    	cout << q.a[5 - n][1] << endl;
    	return 0;
	}
	q = (p ^ (n - 4)) * q;
	cout << q.a[1][1] << endl;
    return 0;
}