题目描述
LJJ 学完了二项式定理,发现这太简单了,于是他将二项式定理等号右边的式子修改了一下,代入了一定的值,并算出了答案。
但人口算毕竟会失误,他请来了你,让你求出这个答案来验证一下。
一共有 T 组数据,每组数据如下:
输入以下变量的值:n,s,a0,a1,a2,a3,求以下式子的值:
i=0∑n((in)⋅si⋅aimod4)mod998244353
其中 (in) 表示 i!(n−i)!n!。
输入格式
第一行一个整数 T,之后 T 行,一行六个整数 n,s,a0,a1,a2,a3。
输出格式
一共 T 行,每行一个整数表示答案。
样例
6
1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5
11
88
253
5576
31813
232
数据范围与提示
对于 50% 的数据,T×n≤105;
对于 100% 的数据,1≤T≤105,1≤n≤1018,1≤s,a0,a1,a2,a3≤108。