该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile6440.zip](file://AdditionalFile6440.zip?type=additional_file)

#6440. 万能欧几里得

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

试求

$$\sum\limits_{x=1}^LA^xB^{\left\lfloor\frac{Px+R}{Q}\right\rfloor}$$

其中 $A,B$ 是 $N$ 行 $N$ 列的矩阵。

输入格式

第一行五个空格隔开的非负整数 $P,Q,R,L,N$ ，其中 $P,Q,L,N$ 均不为 $0$ 。
接下来 $N$ 行，每行 $N$ 个空格隔开的非负整数，其中第 $i$ 行的第 $j$ 个数表示 $A_{i,j}$ 。
接下来 $N$ 行，每行 $N$ 个空格隔开的非负整数，其中第 $i$ 行的第 $j$ 个数表示 $B_{i,j}$ 。

输出格式

共 $N$ 行，每行 $N$ 个空格隔开的非负整数，其中第 $i$ 行的第 $j$ 个数表示 $C_{i,j}$ 模 $998244353$ ，其中 $C$ 是答案矩阵。

样例 1

输入

8 5 2 3 1
1
2

输出

44

样例 2

输入

998244353 654321321 1234567 512 2
123 345
101 233
765 234
606 723

输出

359941153 675459034
50358289 228823864

数据范围与提示

对于 $10\%$ 的数据， $L\leq10^6$ ， $N=1$ ， $A_{1,1}=1$ ， $R=0$ ；
对于 $40\%$ 的数据， $L\leq10^{18}$ ， $N=1$ ， $A_{1,1}=1$ ， $R=0$ ；
对于 $60\%$ 的数据， $L\leq10^{18}$ ， $N=1$ ， $A_{1,1}=1$ ；
对于 $80\%$ 的数据， $L\leq10^{18}$ ， $N\leq20$ ，且 $A$ 是单位矩阵；
对于 $100\%$ 的数据， $L\leq10^{18}$ ， $N\leq20$ ；
对于 $100\%$ 的数据， $P,Q,R,\lfloor\frac{PL}{Q}\rfloor\leq10^{18}$ ， $0\leq A_{i,j},B_{i,j}<998244353$ 。