#6440. 万能欧几里得

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

题目描述

试求

\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

样例输出 1

44

样例输入 2

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

样例输出 2

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