1 矩阵快速幂，好记性不如烂笔头，这是我第二次写这一题了，我先写下博客，方便自己第三次看……啊……

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>

using namespace std;
typedef long long ll;
const ll Mod=2147493647;
const ll maxn=10;
ll N,A,B,T;
struct node
{
	ll jz[maxn][maxn];
};
node Mul(node a,node b)
{
	node res;
	memset(res.jz,0,sizeof(res.jz));
	for(int i=0;i<7;i++)
	{
		for(int j=0;j<7;j++)
		{
			for(int k=0;k<7;k++)
			{
				res.jz[i][j]=(res.jz[i][j]+a.jz[i][k]*b.jz[k][j]%Mod+Mod)%Mod;
			}
		 } 
	}
	return res;
}
node Pow_mod(node a,int b)
{
	node res;
	memset(res.jz,0,sizeof(res.jz));
	for(int i=0;i<7;i++)
	{
		for(int j=0;j<7;j++)
		{
			if(i==j)
			res.jz[i][j]=1;
		}
	 } 
	 while(b)
	 {
	 	if(b&1)
	 	res=Mul(res,a);
		a=Mul(a,a);
		b>>=1; 
	 }
	 return res;
 }
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld",&N,&A,&B);
		if(N==1)
		printf("%lld\n",A);
		else if(N==2)
		printf("%lld\n",B);
		else
		{
			node jie,jie1;
			memset(jie.jz,0,sizeof(jie.jz));
			memset(jie1.jz,0,sizeof(jie1.jz));
			jie.jz[0][0]=1;jie.jz[3][3]=1;
			jie.jz[0][1]=2;jie.jz[3][4]=3;
			jie.jz[0][2]=1;jie.jz[3][5]=3;
			jie.jz[1][0]=1;jie.jz[3][6]=1;
			jie.jz[2][2]=1;jie.jz[4][4]=1;
			jie.jz[2][3]=4;jie.jz[4][5]=2;
			jie.jz[2][4]=6;jie.jz[4][6]=1;
			jie.jz[2][5]=4;jie.jz[5][5]=1;
			jie.jz[2][6]=1;jie.jz[5][6]=1;
			jie1.jz[0][0]=B;jie.jz[6][6]=1;
			jie1.jz[1][0]=A;
			jie1.jz[2][0]=pow(3,4);
			jie1.jz[3][0]=pow(3,3);
			jie1.jz[4][0]=pow(3,2);
			jie1.jz[5][0]=3;
			jie1.jz[6][0]=1;
			node res=Pow_mod(jie,N-2);
			res=Mul(res,jie1);
			printf("%lld\n",res.jz[0][0]);	
		}
	}
	return 0;
}