rt.WA on #10,TLE on #9,#11

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct Matrix
{
	long long a[10][10];
	Matrix()
	{
		memset(a, 0, sizeof(a));
	}
};
const int mod = 1e9 + 7;
Matrix operator * (Matrix x, Matrix y)
{
	Matrix z;
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			for (int l = 1; l <= 2; l++)
			{
				z.a[i][j] += x.a[i][l] * y.a[l][j];
				z.a[i][j] %= mod;
			}
	return z;
}
Matrix fp(Matrix x, int k)
{
	Matrix ret;
	for (int i = 1; i <= 2; i++) ret.a[i][i] = 1;
	while (k)
	{
		if (k & 1) ret = ret * x;
		x = x * x;
		k >>= 1;
	}
	return ret;
}
int main()
{
	long long n;
	scanf("%lld", &n);
	if (n <= 2) 
	{
		puts("1");
		return 0;
	}
	Matrix x;
	x.a[1][1] = x.a[1][2] = x.a[2][1] = 1;
	Matrix y;
	y.a[1][1] = y.a[2][1] = 1;
	Matrix ans = fp(x, n - 2) * y;
	printf("%lld\n", ans.a[1][1]);
	return 0;
}