吉首大学重现赛 A:SARS病毒（矩阵快速幂 + 降幂）

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef long long ll;
#define me(a, b) (memset(a, b, sizeof a))
const ll INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
 
struct M{
	ll m[5][5];
	M()
	{
		me(m, 0);
	}
};
M mul(M a, M b)
{
	M res;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
				res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
	return res;
}
void fpow(ll n)
{
	M a;
	for (int i = 0; i < 4; i++)
		a.m[i][i] = 1;
	M b;
	b.m[0][0] = 2, b.m[0][1] = 1, b.m[0][2] = 1;
	b.m[1][0] = 1, b.m[1][1] = 2, b.m[1][3] = 1;
	b.m[2][0] = 1, b.m[2][2] = 2, b.m[2][3] = 1;
	b.m[3][1] = 1, b.m[3][2] = 1, b.m[3][3] = 2;
	while (n)
	{
		if (n & 1)
			a = mul(a, b);
		n >>= 1;
		b = mul(b, b);
	}
	M res;
	res.m[0][0] = 2, res.m[1][0] = 1, res.m[2][0] = 1;
	res = mul(a, res);
	cout << res.m[0][0] % mod << endl;
}
int main(){
	string s;
	while (cin >> s)
	{
		ll b = 0;
		int len = sz(s);
		for (int i = 0; i < len; i++)
		{
			b = (b * 10 + s[i] - '0') % (mod - 1);
		}
		fpow(b - 1);
	}
	return 0;
}