Given the value of a+b and ab you will have to find the value of an+bn. a and b not necessarily have to be real numbers.

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

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 00.

Output
For each test case, print the case number and (an+bn) modulo 264.

Sample Input
2

10 16 2

7 12 3

Sample Output
Case 1: 68

Case 2: 91

[latex]a^n+b^n 很容易想到和a^(n-1)+b^(n-1)[/latex]相关。再乘上初始的[latex]a+b[/latex]。有一个量总是不变化的，所以想到矩阵。演算几下可以发现[latex](f(n-1) f(n-2)) \begin{matrix} a+b & 1 \\ -ab & 0 \\ \end{matrix} \tag{1} = (f(n) f(n-1))[/latex]

题目%2^64，可以直接用ull类型。注意！ull在scanf里面是“%llu”而不是lld。我因为这个wa了一发

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
struct Mat{
	ll a[5][5];
	Mat(){
		memset(a,0,sizeof(a));
	}
};
Mat mul(Mat a,Mat b)
{
	Mat res=Mat();
	for(ll i=1;i<=2;i++)
	{
		for(ll j=1;j<=2;j++)
		{
			for(ll k=1;k<=2;k++)
			{
				res.a[i][j]+=a.a[i][k]*b.a[k][j];	
			}	
		}	
	}	
	return res;
} 
Mat ksm(Mat n,ll k)
{
	Mat ans=Mat();
	for(ll i=1;i<=2;i++)
	ans.a[i][i]=1;
	while(k)
	{
		if(k&1) ans=mul(n,ans);
		n=mul(n,n);
		k>>=1;
	}
	return ans;
}
Mat mul2(Mat a,Mat b)
{
	Mat res=Mat();
	for(ll i=1;i<=1;i++)
	{
		for(ll j=1;j<=2;j++)
		{
			for(ll k=1;k<=2;k++)
			{
				res.a[i][j]+=a.a[i][k]*b.a[k][j];	
			}	
		}	
	}	
	return res;
} 
int main()
{
	ll t,q,p,n;
	scanf("%llu",&t);
	for(ll i=1;i<=t;i++)
	{
		scanf("%lld%lld%lld",&p,&q,&n);
		Mat p1=Mat();
		p1.a[1][1]=p;p1.a[1][2]=1;
		p1.a[2][1]=-q;p1.a[2][2]=0;
		Mat f=Mat();
		f.a[1][1]=p;f.a[1][2]=2;
		printf("Case %llu: ",i);
		if(n==0) 
		{
			printf("2\n");
			continue;
		}
		Mat p2=ksm(p1,n-1);
		Mat a1=mul2(f,p2);
		printf("%llu\n",a1.a[1][1]);
	} 
	
}