#6485. LJJ 学二项式定理

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 284914869

题目描述

LJJ 学完了二项式定理,发现这太简单了,于是他将二项式定理等号右边的式子修改了一下,代入了一定的值,并算出了答案。

但人口算毕竟会失误,他请来了你,让你求出这个答案来验证一下。

一共有 T T 组数据,每组数据如下:

输入以下变量的值:n,s,a0,a1,a2,a3 n, s , a_0 , a_1 , a_2 , a_3,求以下式子的值:

[i=0n((ni)siaimod4)]mod998244353\Large \left[ \sum_{i=0}^n \left( {n\choose i} \cdot s^{i} \cdot a_{i\bmod 4} \right) \right] \bmod 998244353

其中 (ni) n\choose i 表示 n!i!(ni)! \frac{n!}{i!(n-i)!}

输入格式

第一行一个整数 TT,之后 TT 行,一行六个整数 n,s,a0,a1,a2,a3n, s, a_0, a_1, a_2, a_3

输出格式

一共 TT 行,每行一个整数表示答案。

样例

样例输入

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% 50\% 的数据,T×n105 T \times n \leq 10^5

对于 100% 100\% 的数据,1T105,1n1018,1s,a0,a1,a2,a3108 1 \leq T \leq 10^5, 1 \leq n \leq 10 ^ {18}, 1 \leq s, a_0, a_1, a_2, a_3 \leq 10^{8}