题目描述

神犇是某少女附中的高三生。在机房的窗边，神犇和 LCR 一起俯瞰着楼下玩篮球的学生。注视着他们的背影，神犇想起了高一时的一件往事 ……

当时，他的体育老师每节体育课都让同学们玩传球游戏，玩法是这样的：

体育老师有 $n$ 个篮球。一开始，体育老师会把所有学生平均分为 $n$ 组，每组 $m$ 人。组的编号为 $0,1,\cdots,n-1$，每组中学生分别编号为 $0,1,\cdots,m-1$。为了方便描述，我们定义 $S$ 为 $[0,m)$ 中的整数集合。

接着，体育老师会使用他手机上的计算器生成一个长为 $n$ 的每个元素属于 $S$ 的伪随机数列 $\{s_i\}$。接着对于第 $i$ 组他把球发给该组的 $s_i$ 号学生。

然后体育老师会发给学生一个 $m\times m$ 的表 $A$ 表示传球规则，其中的数都属于 $S$，且 $A$ 有一些特殊性质。为了方便描述 $A$，我们定义 $S$ 上的二元运算 $\circ:i\circ j=A_{i,j}$。另外定义 $ i^j = \begin{gather}\underbrace{i\circ i\circ \cdots \circ i}\\ j \text{ times} \end{gather} $。
$A$ 满足的性质如下：

• 交换律，即 $\forall i,j \in S,i\circ j=j\circ i$
• 结合律，即 $\forall i,j,k \in S,(i\circ j)\circ k=i\circ (j \circ k)$
• 循环律，即 $\forall i\in S,\exists j>1$ 使得 $i^j=i$

然后体育老师会让学生进行 $k$ 轮传球。每一轮传球的方法相同，如下：

• 首先体育老师会使用他手机上的计算器生成一个长为 $n$ 的每个元素属于 $S$ 的伪随机数列 $\{s_i\}$。
• 对于第 $i$ 组学生，如果当前球在组内编号为 $a_i$ 的学生手上，那么他会把球传给组内 $a_i\circ s_i$ 号学生（当 $a_i = a_i\circ s_i$ 时不传球）。

为了方便，我们用一个 $n$ 位 $m$ 进制数来表示一个长为 $n$，下标从 $0$ 开始，每个位置元素属于 $S$ 的数列。具体地，我们用 $\sum_{i=0}^n s_i m^i$ 来表示 $\{s_i\}$。显然，$[0,m^n)$ 中的整数与所有可能的该种数列一一对应。

神犇记得，体育老师手机里的随机数生成器生成的每组随机数的 $m^n$ 种结果并不是等可能的（但同一节课内每次使用时生成各结果的概率不变）。我们用一个长 $m^n$ 的序列 $\{P_i\}$ 表示每种结果的概率，设 $X=\sum_{i=0}^{m^n-1} P_i$，则生成 $i$ 对应的数列的概率为 $\frac{P_i}{X}$。

神犇把这些往事告诉了 LCR。LCR 想知道 $k$ 轮传球后球的持有者的每种情况的概率。于是她希望你 —— 某少女附中著名 OIer —— 来解决这个问题。

设最终编号为 $i$ 的组中篮球在 $r_i$ 号学生手中，那么用 $\{r_i\}$ 对应的 $m$ 进制数来表示这个状态。为了简化计算及避免精度误差，我们只需要求出对于 $[0,m^n)$ 中的每个数 $i$，$i$ 所对应的状态的概率与 $X^{k+1}$ 的乘积模 $232792561$ 的值。

输入格式

第一行三个整数 $n,m,k$。
接下来 $m$ 行每行 $m$ 个整数，表示 $A$。其中第 $i+1$ 行第 $j+1$ 个整数表示 $A_{i,j}$。
接下来一行 $m^n$ 个整数，其中第 $i+1$ 个整数表示 $P_i$。

输出格式

输出 $m^n$ 行，每行一个整数，其中第 $i+1$ 行表示 $k$ 次传球过后处于 $i$ 所对应的状态的概率与 $X^{k+1}$ 的乘积模 $232792561$ 的值。

2 2 1
0 1
1 0
3 2 4 1

30
20
28
22

3 2 2
0 1
1 0
1 2 1 2 1 0 0 3

118
134
118
134
130
114
102
150

3 3 1000000000000000000
0 1 0
1 0 1
0 1 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

213274696
208936145
25902863
95562855
217079278
63925718
106613073
183344989
8375316
32956358
199136079
5516750
230547873
170961061
216818160
114420143
15437393
149522201
77102517
62329524
215121795
51813646
230286755
91113233
13573868
80597355
39406187

数据范围与提示

对于所有数据，$1\le n\le 18,2\le m\le 22,1\le k\le 10^{18},m^n\le 5\times 10^5 ,0\le P_i < 232792561$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

注：特殊限制中的矩阵，从上到下第 $i+1$ 行从左到右第 $j+1$ 列表示 $A_{i,j}$。