#P18560. World of Rains
World of Rains
World of Rains
Little Cyan Fish 正在探索一个雨的世界!这个二维世界用一个 的网格表示。第 行、第 列的格子记作 ,其中 、。
一只神奇的猫控制着这个世界的降雨。降雨过程持续 秒,依次编号为 。初始时刻为0,即第一秒开始前,任何格子中都没有水滴。

在每一秒 ()中,按以下顺序发生这些事件:
- 降雨:对于每一个当前没有水滴的格子,猫独立、随机地决定是否在这个格子中创造一滴新水滴。
- 移动(第 秒除外):若 ,所有已经存在的水滴同时受重力和风的影响而移动。位于 的水滴移动到 。
- 消失:移动到 网格范围外的水滴会永久消失。
你需要计算不同的可能降雨情景的数量。
当且仅当存在某个格子 和某个时刻 (),使得一个情景在该格子、该时刻创造了新水滴,而另一个情景没有,两个情景才被认为不同。
答案可能很大,请将结果对 取模后输出。
输入格式
第一行包含整数 (),表示测试用例数。
对于每个测试用例:
第一行包含三个整数 ()。
第二行包含 个整数 ()。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一行整数,表示不同降雨情景的数量对 取模的结果。
原样例
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