这个问题怎么搞呢

显然是个递推式，可是有个$i^4$

把它展开，就可以完全递推了。

关于递推式的一点点理解

首先把需要递推的东西列为一列，不妨记长度为L，另外一边可以搞一个对应的L*L的矩阵（先前矩阵其余部分用0填充）

其中每一行的每一个数也就对应的那一列中的元素的系数。

如此如此，这般这般。

矩阵冲冲冲

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=2147493647;
ll n,a,b;
struct re{
    int rec[8][8];
}ans,tem,org,m;
int t;
void ini1(){
     m.rec[0][0] = b,m.rec[0][1] = 0,m.rec[0][2] = 0,m.rec[0][3] = 0,m.rec[0][4] = 0,m.rec[0][5] = 0,m.rec[0][6] = 0;
        m.rec[1][0] = a,m.rec[1][1] = 0,m.rec[1][2] = 0,m.rec[1][3] = 0,m.rec[1][4] = 0,m.rec[1][5] = 0,m.rec[1][6] = 0;
        m.rec[2][0] = 16,m.rec[2][1] = 0,m.rec[2][2] = 0,m.rec[2][3] = 0,m.rec[2][4] = 0,m.rec[2][5] = 0,m.rec[2][6] = 0;
        m.rec[3][0] = 8,m.rec[3][1] = 0,m.rec[3][2] = 0,m.rec[3][3] = 0,m.rec[3][4] = 0,m.rec[3][5] = 0,m.rec[3][6] = 0;
        m.rec[4][0] = 4,m.rec[4][1] = 0,m.rec[4][2] = 0,m.rec[4][3] = 0,m.rec[4][4] = 0,m.rec[4][5] = 0,m.rec[4][6] = 0;
        m.rec[5][0] = 2,m.rec[5][1] = 0,m.rec[5][2] = 0,m.rec[5][3] = 0,m.rec[5][4] = 0,m.rec[5][5] = 0,m.rec[5][6] = 0;
        m.rec[6][0] = 1,m.rec[6][1] = 0,m.rec[6][2] = 0,m.rec[6][3] = 0,m.rec[6][4] = 0,m.rec[6][5] = 0,m.rec[6][6] = 0;    
}
void ini2(){
      org.rec[0][0] = 1,org.rec[0][1] = 2,org.rec[0][2] = 1,org.rec[0][3] = 4,org.rec[0][4] = 6,org.rec[0][5] = 4,org.rec[0][6] = 1;
        org.rec[1][0] = 1,org.rec[1][1] = 0,org.rec[1][2] = 0,org.rec[1][3] = 0,org.rec[1][4] = 0,org.rec[1][5] = 0,org.rec[1][6] = 0;
        org.rec[2][0] = 0,org.rec[2][1] = 0,org.rec[2][2] = 1,org.rec[2][3] = 4,org.rec[2][4] = 6,org.rec[2][5] = 4,org.rec[2][6] = 1;
        org.rec[3][0] = 0,org.rec[3][1] = 0,org.rec[3][2] = 0,org.rec[3][3] = 1,org.rec[3][4] = 3,org.rec[3][5] = 3,org.rec[3][6] = 1;
        org.rec[4][0] = 0,org.rec[4][1] = 0,org.rec[4][2] = 0,org.rec[4][3] = 0,org.rec[4][4] = 1,org.rec[4][5] = 2,org.rec[4][6] = 1;
        org.rec[5][0] = 0,org.rec[5][1] = 0,org.rec[5][2] = 0,org.rec[5][3] = 0,org.rec[5][4] = 0,org.rec[5][5] = 1,org.rec[5][6] = 1;
        org.rec[6][0] = 0,org.rec[6][1] = 0,org.rec[6][2] = 0,org.rec[6][3] = 0,org.rec[6][4] = 0,org.rec[6][5] = 0,org.rec[6][6] = 1;
}
re tim(re x,re y){
    for(int i=0;i<7;++i){
        for(int j=0;j<7;++j){
            tem.rec[i][j]=0;
            for(int k=0;k<7;++k){
                tem.rec[i][j]=x.rec[i][k]*y.rec[k][j];
                tem.rec[i][j]%=mod;
            }
        }
    }
    return tem;
}
re power(int n){
    re temm=org;
    while(n){
        if(n&1){
            org=tim(temm,org);
        }
        n>>=1;
        temm=tim(temm,temm); 
    } 
    return org;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&a,&b);
        if(n==1){
            cout<<a%mod;
            continue ;
        }
        if(n==2){
            cout<<b%mod;
            continue ;
        }
        ini1();
        ini2(); 
        m=tim(power(n-3),m);
        cout<<m.rec[0][0]%mod<<endl; 
    } 
    return 0;
}