这是我接管阿烜的博客后的第一篇题解，还是好好写一写罢。
我们可以考虑枚举\(i\)，用矩阵来快速计算第二种转移的方式，这需要我们对于\(\forall i\in [1,n]\)快速求出\(f(i)=\sum_{j=1}^n\binom{i+j}{j}b^j\)，其中\(b\)是第二种转移方式的转移矩阵。
对于\(f(i+1)\)，用递推的方法来解决他：
\[\begin{aligned} &f(i+1)=\sum_{j=1}^n\binom{i+1+j}{j}b^j\\ =&\sum_{j=1}^n\binom{i+j}{j}b^j+\sum_{j=1}^n\binom{i+j}{j-1}b^j\\ =&f(i)+\sum_{j=0}^{n-1}\binom{i+j+1}{j}b^{j+1}\\ =&f(i)+b(f(i+1)-\binom{i+1+n}{n}b^n+1)\\ =&f(i)+f(i+1)\times b-\binom{i+1+n}{n}b^{n+1}+b\\ \end{aligned} \]由此我们可以得出\(f(i)=f(i+1)-f(i+1)\times b+\binom{i+1+n}{n}b^{n+1}-b\)，尽管我们最开始的目的是得到一个可以求出\(f(i+1)\)的递推式，但最后却阴差阳错得到这个式子可以倒推求出所有\(f\)，也满足我们的需求了。
上代码：
#include<bits/stdc++.h>
#define re signed
#define LL long long
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-48,c=getchar();return x;
}
const int mod=998244353;
const int maxn=2e5+15;
int n,a,b,c,d,e,fac[maxn],ifac[maxn],g[maxn>>1];
inline int dqm(int x) {return x<0?x+mod:x;}
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int ksm(int a,int b) {
int S=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)S=1ll*S*a%mod;return S;
}
struct mat{int a[2][2];}C,f[maxn>>1],v,prd;
inline mat operator*(const mat &A,const mat &B) {
C.a[0][0]=qm(1ll*A.a[0][0]*B.a[0][0]%mod+1ll*A.a[0][1]*B.a[1][0]%mod);
C.a[0][1]=qm(1ll*A.a[0][0]*B.a[0][1]%mod+1ll*A.a[0][1]*B.a[1][1]%mod);
C.a[1][0]=qm(1ll*A.a[1][0]*B.a[0][0]%mod+1ll*A.a[1][1]*B.a[1][0]%mod);
C.a[1][1]=qm(1ll*A.a[1][0]*B.a[0][1]%mod+1ll*A.a[1][1]*B.a[1][1]%mod);
return C;
}
inline mat operator+(const mat &A,const mat &B) {
C.a[0][0]=qm(A.a[0][0]+B.a[0][0]);
C.a[0][1]=qm(A.a[0][1]+B.a[0][1]);
C.a[1][0]=qm(A.a[1][0]+B.a[1][0]);
C.a[1][1]=qm(A.a[1][1]+B.a[1][1]);
return C;
}
inline mat operator-(const mat &A,const mat &B) {
C.a[0][0]=dqm(A.a[0][0]-B.a[0][0]);
C.a[0][1]=dqm(A.a[0][1]-B.a[0][1]);
C.a[1][0]=dqm(A.a[1][0]-B.a[1][0]);
C.a[1][1]=dqm(A.a[1][1]-B.a[1][1]);
return C;
}
inline mat operator^(int val,const mat &B) {
C.a[0][0]=1ll*val*B.a[0][0]%mod;
C.a[0][1]=1ll*val*B.a[0][1]%mod;
C.a[1][0]=1ll*val*B.a[1][0]%mod;
C.a[1][1]=1ll*val*B.a[1][1]%mod;
return C;
}
inline int bin(int n,int m) {
return m>n?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main() {
int N=200000;fac[0]=ifac[0]=1;
for(re int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[N]=ksm(fac[N],mod-2);
for(re int i=N-1;i;--i)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
for(re int T=read();T;--T) {
n=read(),a=read(),b=read(),c=read(),d=read(),e=read();
f[n].a[0][0]=f[n].a[0][1]=f[n].a[1][0]=f[n].a[1][1]=0;
v.a[0][0]=0,v.a[0][1]=1,v.a[1][0]=e,v.a[1][1]=d;prd=v;
for(re int j=1;j<=n;j++)
f[n]=f[n]+(bin(j+n,j)^prd)，prd=prd*v;
for(re int i=n-1;i;--i)
f[i]=f[i+1]-v*f[i+1]-v+(bin(i+1+n,n)^prd);
g[0]=0,g[1]=a;int ans=0;
for(re int i=2;i<=n;i++)g[i]=qm(1ll*b*g[i-1]%mod+1ll*c*g[i-2]%mod);
for(re int i=1;i<=n;i++) {
ans=qm(ans+1ll*g[i-1]*f[i].a[1][0]%mod);
ans=qm(ans+1ll*g[i]*f[i].a[1][1]%mod);
}
printf("%d\n",ans);
}
return 0;
}