#P18560. World of Rains

World of Rains

World of Rains

Little Cyan Fish 正在探索一个雨的世界!这个二维世界用一个 N×MN\times M 的网格表示。第 ii 行、第 jj 列的格子记作 (i,j)(i,j),其中 1≤i≤N1\le i\le N、1≤j≤M1\le j\le M。

一只神奇的猫控制着这个世界的降雨。降雨过程持续 S+1S+1 秒,依次编号为 1,2,…,S+11,2,\ldots,S+1。初始时刻为0,即第一秒开始前,任何格子中都没有水滴。

原题中的雨中猫插图

在每一秒 ii(1≤i≤S+11\le i\le S+1)中,按以下顺序发生这些事件:

  1. 降雨:对于每一个当前没有水滴的格子,猫独立、随机地决定是否在这个格子中创造一滴新水滴。
  2. 移动(第 S+1S+1 秒除外):若 i≤Si\le S,所有已经存在的水滴同时受重力和风的影响而移动。位于 (x,y)(x,y) 的水滴移动到 (x+1,y+di)(x+1,y+d_i)。
  3. 消失:移动到 N×MN\times M 网格范围外的水滴会永久消失。

你需要计算不同的可能降雨情景的数量。

当且仅当存在某个格子 (i,j)(i,j) 和某个时刻 tt(1≤t≤S+11\le t\le S+1),使得一个情景在该格子、该时刻创造了新水滴,而另一个情景没有,两个情景才被认为不同。

答案可能很大,请将结果对 998244353998244353 取模后输出。

输入格式

第一行包含整数 TT(T≥1T\ge1),表示测试用例数。

对于每个测试用例:

第一行包含三个整数 N,M,SN,M,S(1≤N,M,S≤5×1051\le N,M,S\le5\times10^5)。

第二行包含 SS 个整数 d1,d2,…,dSd_1,d_2,\ldots,d_S(−109≤di≤109-10^9\le d_i\le10^9)。

保证所有测试用例的 SS 之和不超过 5×1055\times10^5。

输出格式

对于每个测试用例,输出一行整数,表示不同降雨情景的数量对 998244353998244353 取模的结果。

原样例

3
2 2 1
1
3 3 5
1 0 0 0 -1
9 10 7
1 4 -2 -8 5 -7 142857
192
536867776
736446321