#1174. 「GuOJ Round #1」勇者

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

题目描述

静けき森の中 いま目覚めた花たちよ

在寂静的森林中 如今苏醒的花儿们

この世に何を思い 何を感じてる

与这世间感受到了什么


咲き誇れ(咲き誇れ) 想いのままに

如今骄傲的绽放吧(骄傲的绽放吧)怀着这样的念想

この瞬間(この瞬間) 全てを賭けて

在这一瞬间(这一瞬间) 赌上一切

無限の星すらも霞むように

就连无限的星光也开始变得朦胧

勇気 心に溢れ

勇气溢满了内心

(いかなる)いかなる時も生きて

无论何时都一定要活下去

神世纪300年,少女们的物语,勇者们的传说...

虚幻的美好,支离破碎的世界,故事由此展开...


为了探究大家身体变化的本质原因,小鱼干(三好夏凛)给了你(大赦高层)一个 (n+1)\times m 的网格。

对任意的整数 i,j,k(0\le i< n,1\le j,k\le m) ,格子 (i,j) w_{j,k} 种方式移动到格子 (i+1,k)

小鱼干的初始位置在 (0,x) ,她想知道有多少种方法到达某一个位置。

具体的,她会给你两个正整数 p,y ,你需要回答她对于每个 0\le t<p 的整数 t ,她有多少种方法可以到达格子 (t,y),(t+p,y),(t+2p,y),\dots,(t+\lfloor \frac{n-t}{p} \rfloor p,y) ,你只需要分别对于每个 t 告诉她到达这些格子的方案数的和 \bmod 998244353 就可以了。

输入格式

第一行两个整数 n,m 表示行和列。

接下来第 2 至第 m+1 行,每行 m 个整数,第 i 行第 j 个整数表示 w_{i-1,j}

m+2 行,三个正整数 p,x,y

输出格式

输出共 p 行,每行一个整数,第 i 行表示 t=i-1 时的答案。

样例

样例 1 输入

2 2
1 2
0 1
2 1 2

样例 1 输出

4
2

样例 1 解释

格子上的数字代表方案数

t=0 时,方案数为 0+4=4

t=1 时,方案数为 2

数据范围与提示

子任务编号 子任务分值 n\le m 特殊性质
1 15 \le 10^6 \le 6
2 25 \le 10^{18} =1
3 24 \le 6 保证 w [0,998244353)\cap\mathbb Z 范围内均匀随机
4 36

对于 100\% 的数据,满足 1\le n\le 10^{18} 1\le m\le 6 2\le p\le 100000 0\le w_{i,j}< 998244353 1\le x,y\le m