神犇是某少女附中的高三生。在机房的窗边，神犇和 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$ 的值。
LibreOJ