#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL MOD = 1e9+7;

struct Matrix{
	LL a[2][2];
	
	Matrix operator * (Matrix b){
		Matrix ret;
		memset(ret.a,0,sizeof(ret.a));
		
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<2;k++){
					ret.a[i][j] += (a[i][k] + b.a[k][j] + 10LL*MOD)%MOD;
					ret.a[i][j] %= MOD;
				}
			}
		}
		return ret;
	}
	
	Matrix operator - (Matrix b){
		Matrix ret;
		
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				ret.a[i][j] = (a[i][j] - b.a[i][j] + 10LL*MOD) % MOD;
			}
		}
		return ret;
	}
	
};

LL fe(LL x, LL p){
	if(p==0) return 1LL;
	if(p==1) return x;
	LL ret = fe(x,p/2);
	ret = ret*ret;
	ret%=MOD;
	if(p&1){
		ret = ret*x;
		ret%=MOD;
	}
	return ret;
}

Matrix inver(Matrix x){
	LL tmp = (x.a[0][0]*x.a[1][1])%MOD;
	cout << tmp << "<" << endl;
	tmp -= (x.a[0][1] * x.a[1][0])%MOD;
	tmp+=MOD;
	tmp%=MOD;
	cout << "--- " << tmp << endl;
	tmp = fe(tmp,MOD-2);
	cout << ">>> " << tmp << endl;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			x.a[i][j] = (x.a[i][j]*tmp)%MOD;
			if(i+j == 1) x.a[i][j]*=-1, x.a[i][j] = (x.a[i][j] + MOD)%MOD;
		}
	}
	swap(x.a[0][0],x.a[1][1]);
	return x;
}

Matrix iden;
Matrix fem(Matrix &x, LL p){
	if(p==0) return iden;
	if(p==1) return x;
	Matrix ret = fem(x,p/2);
	ret = ret*ret;
	if(p&1) ret = ret*x;
	return ret;
}

Matrix aw;
Matrix rek;

void pre(){
	memset(iden.a,0,sizeof(iden.a));
	for(int i=0;i<2;i++) iden.a[i][i] = 1;
	memset(aw.a,0,sizeof(aw.a));
	aw.a[0][1] = 1;
	memset(rek.a,0,sizeof(rek.a));
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			if(i+j == 0) continue;
			rek.a[i][j] = 1;
		}
	}
}

void print(Matrix x){
	printf("////////////////////\n");
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			printf("%lld ",x.a[i][j]);
		}
		printf("\n");
	}
}

int tc;
LL n;
int c,k;

int main(){
	pre();
//	cout << -fe(123,MOD-2)+MOD << " " << fe(-123,MOD-2)+MOD << endl;
	scanf("%d",&tc);
	for(int ii=1;ii<=tc;ii++){
		scanf("%lld %d %d",&n,&c,&k);
		Matrix B = fem(rek,c);
		Matrix dep = fem(aw,k);
		print(dep);
		print(B);
		Matrix bk = fem(B,k);
		print(bk);
		Matrix bkn = fem(bk,n+1);
		bk = bk - iden;
		print(bk);
		bk = inver(bk);
		print(bk);
		bkn = bkn - iden;
		dep = dep*bkn;
		dep = dep*bk;
		printf("Case %d: ",ii);
		printf("%lld\n",dep.a[0][0]);
	}
	return 0;
}