白兔的式子
题号:NC15251
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

已知f[1][1]=1,f[i][j]=a*f[i-1][j]+b*f[i-1][j-1](i>=2,1<=j<=i)
对于其他情况f[i][j]=0

T组询问,每次给出a,b,n,m,求f[n][m] mod (998244353)

输入描述:

第一行为一个整数T,表示询问个数。
接下来一共T行,每行四个整数a,b,n,m。

输出描述:

一共T行,每行一个整数,表示f[n][m] mod (998244353)
示例1

输入

复制
2
2 3 3 3
3 1 4 1

输出

复制
9
27

备注:

T<=100000

1<=m<=n<=100000

0<=a,b<=109