题目描述

一句话题意：

给定一个 $p \times q$ 次的二元多项式 $F(x, y)$，求

$$\sum_{x = 0}^n \sum_{y = 0}^{\min(x, m)} \binom{x + y}{x} \binom{n - x + m - y}{n - x} F(x, y)$$

对 $998244353$ 取模的结果。

每个测试点有 $T$ 组询问，保证所有询问中 $m - n$ 的值是一个常数 $c$。

输入格式

第一行输入五个整数 $T, c, p, q, N$，分别表示询问数量，$m - n = c$，二元多项式的次数以及此测试点询问中 $n$的上限，即保证此测试点中所有询问满足 $n \leq N$。

接下来输入 $T$ 组测试数据，每组测试数据输入方式如下：

第一行两个整数 $n$ 和 $m$， 保证满足 $m - n = c$ 。

接下来 $p + 1$ 行每行 $q + 1$ 个数，第 $i$ 行第 $j$ 个数表示 $F(x, y)$ 中 $x^{i - 1} y^{j - 1}$ 的系数。

输出格式

输出 $T$ 行，每行一个整数表示题目中所求的答案。

样例数据

input

2 0 1 1 5
1 1 
1 1
1 1
2 2
1 2
3 4

output

12
278

数据范围

为了方便，以下记 $L = \max(N, N + c)$ ，即询问中坐标的范围。

对于所有测试数据：$1 \leq T \leq 10^5, -10^5 \leq c \leq 10^5, 1 \leq L \leq 10^5, 0 \leq (p + 1) \times (q + 1) \leq 10$。保证输入的多项式的系数属于 $[0, 998244353)$ 。

subtask 1 ($1$ pts)：$T = 1, L \leq 10^3$

subtask 2 ($9$ pts)：$L \leq 10^3$

subtask 3 ($20$ pts)：$T = 1, p = q = 0$

subtask 4 ($20$ pts)：$p = q = 0$

subtask 5 ($20$ pts)：$T = 1$

subtask 6 ($10$ pts)：$c = 0$

subtask 7 ($20$ pts)：没有特殊限制。

时间限制：1.5s

空间限制：512MB