You have to find the nth term of the following function:

f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2)

     = 0, if(n ≤ 2)

Input
Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output
For each case, print the case number and f(n) modulo 10007.

Sample Input
2

10 1 2 3

5 1 3 9

Sample Output
Case 1: 162

Case 2: 27

矩阵快速幂。就是快速幂的乘运算换成了矩阵乘运算。递推数列写成矩阵形式。

第一次交TLE了，下来吧输入改成scnaf，加了个n<=2的特判，就过了

a 0 b c        f[n-1]       f[n]
1 0 0 0        f[n-2[       f[n-1]
0 1 0 0        f[n-3]       f[n-2]
0 0 0 1           1             1

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace std;

struct mt{
	int mmt[10][10];
}ans,res;
int t,hn,ha,hb,hc;
mt mul(mt a,mt b,int n)
{
	mt tmp;
	memset(tmp.mmt,0,sizeof(tmp.mmt));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				tmp.mmt[i][j]+=a.mmt[i][k]*b.mmt[k][j];
				tmp.mmt[i][j]%=10007;
			}
		}
	} 
	return tmp;
}
void mtqkpow(int a,int n)
{
	for(int i=1;i<=n;i++) ans.mmt[i][i]=1;
	while(a)
	{
		if(a&1) ans=mul(ans,res,n);
		res=mul(res,res,n);
		a>>=1;
	} 
}
int main()
{
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		memset(ans.mmt,0,sizeof(ans.mmt));
		memset(res.mmt,0,sizeof(res.mmt));
		scanf("%d%d%d%d",&hn,&ha,&hb,&hc);
		if(hn<=2){
			printf("Case %d: 0\n",i);
			continue;
		}
		res.mmt[1][1]=ha;
		res.mmt[1][3]=hb;
		res.mmt[1][4]=hc;
		res.mmt[2][1]=1;
		res.mmt[3][2]=1;
		res.mmt[4][4]=1;
		mtqkpow(hn-1,4);
		mt m;
		memset(m.mmt,0,sizeof(m.mmt));
		m.mmt[1][1]=hc;
		m.mmt[4][1]=1;
		int anser=0;
		for(int k=1;k<=4;k++)
		{
			anser+=ans.mmt[3][k]*m.mmt[k][1];
			anser%=10007;
		}
		printf("Case %d: %d\n",i,anser);
	}
}