题目： 大家都知道，斐波那契数列是满足如下性质的一个数列： $F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$ 请你求出 $F_n \bmod 10^9 + 7$ 的值。

#include <iostream>
const long long MOD = 1e9 + 7;
struct Matricx {
	long long matricx[4][4];
} Base, Ans;
Matricx multiply(Matricx a, Matricx b, int n) {
	Matricx ans;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				int temp = a.matricx[i][k] * b.matricx[k][j] % MOD;
				ans.matricx[i][j] = (ans.matricx[i][j] + temp) % MOD;
			}
		}
	}
	return ans;
}
Matricx quickpow(Matricx a, int n, long long k) {
	Matricx ans = a;
	while (k != 0) {
		if (k % 2 == 1)
			ans = multiply(ans, a, n);
		a = multiply(a, a, n);
		k = k / 2;
	}
	return ans;
}
int main() {
	int n;
	std::cin >> n;
	if (n == 1 || n == 2) {
		std::cout << 1;
		return 0;
	}
	n = n - 2;
	Matricx Base;
	Base.matricx[1][1] = 1;
	Base.matricx[1][2] = 1;
	Base.matricx[2][1] = 1;
	Base.matricx[2][2] = 0;
	Ans = quickpow(Base, 2, n);
	long long res = (Ans.matricx[1][1] * 1 + Ans.matricx[1][2] * 1) % MOD;
	std::cout << res;
	return 0;
}

20分，其余WA。