黑白球

Problem Description

考虑如下问题：

长为 $n$ 的数轴上，坐标 $i$（$0\leq i\lt n$）有 $a_i$ 个黑球，$m-a_i$ 个白球，任意两个球都是可区分的。 对于一个 $0\sim n-2$ 的排列 $p$，按顺序遍历所有 $i$（$0\leq i\lt n-1$），执行如下操作： 在坐标 $p_i,p_i+1$ 上分别选择球 $x,y$，将球 $x$ 的颜色改为球 $y$ 的颜色。

求在所有 $\left(n-1\right)!m^{2\left(n-1\right)}$ 情况下结束时数轴上黑球的个数和。

现在给定 $n,m,k$ 和初始序列 $a_0,a_1,\ldots ,a_{n-1}$。 保证 $n$ 是 $2$ 的幂 。令 $f\left(a\right)$ 表示序列 $a_0,a_1,\ldots ,a_{n-1}$ 关于上述问题的答案。 执行 $i$（$0\le i \lt k$）次操作，每次交换序列中相邻两个元素，求对于所有 $\left(n-1\right)^i$ 种可能的操作，操作后，$f\left(a\right)$ 的和对 $998244353$ 取模。

Input

第一行输入一个正整数 $T$（$1\le T \le 20$），表示数据组数。 对于每组数据，第一行包含三个正整数 $n,m,k$（$2\le k\le n\le 2^{17}$，$2\le m < 998244353$，保证 $n$ 为 $2$ 的幂）。 第二行包含 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$（$1\le a_i \le m$）。

Output

对于每组数据，输出 $k$ 行，每行一个整数，第 $i$ 行表示操作 $i-1$ 次的答案。

Sample Input

1
2 2 2
1 2

Sample Output

14
10

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（5）