给定一个数组 $$$a$$$,大小为 $$$n$$$ ($$$1 \leq a_i \leq m$$$)。
考虑数组 $$$[1, 2, \ldots, m]$$$ 的所有 $$$m!$$$ 排列。对于任何排列 $$$p$$$,将数组 $$$b_p$$$ 定义为通过连接数组 $$$a$$$ 和排列 $$$p$$$ 形成的数组。更正式地说,$$$b_p = [a_1, a_2, \ldots, a_n, p_1, p_2, \ldots, p_m]$$$。
设 $$$f(i)$$$ 表示排列 $$$p$$$ 的数量,使得数组 $$$b_p$$$ 恰好包含 $$$i$$$ 回文 $$$^{\text{*}}$$$ 的子数组 偶数长度.
您的任务是计算 $$\sum_{i=0}^{10^{100}} f(i)^{i+1}.$$
由于答案可能很大,因此应该以 $$$998\,244\,353$$$ 为模进行计算。
$$$^{\text{*}}$$$数组 $$$[c_1, c_2, \ldots, c_k]$$$ 被认为是回文数组,如果 $$$c_i = c_{k+1-i}$$$ 对于所有 $$$1 \le i \le k$$$ 来说是回文数组。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 10^6$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — 数组的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,在新行上打印一个整数 - $$$\sum_{i=0}^{10^{100}} f(i)^{i+1}$$$ 模 $$$998\,244\,353$$$。
示例
输入复制
54 33 1 2 11 119 44 1 2 1 3 3 1 2 16 31 1 3 1 1 110 64 4 1 2 1 3 3 1 2 1
输出复制
61124896025814006753
注意
在第一个测试用例中,$$$n=4$$$、$$$m=3$$$ 和 $$$a=[3,1,2,1]$$$。
让我们列出所有排列并计算偶数长度的回文子数组的数量:
- $$$p_1 = [1, 2, 3]$$$, $$$b_{p_1} = [3, 1, 2, 1, 1, 2, 3]$$$,偶数长度的回文子数组的数量为$$$2$$$。
- $$$p_2 = [1, 3, 2]$$$, $$$b_{p_2} = [3, 1, 2, 1, 1, 3, 2]$$$,偶数长度的回文子数组的数量为 $$$1$$$。
- $$$p_3 = [2, 1, 3]$$$, $$$b_{p_3} = [3, 1, 2, 1, 2, 1, 3]$$$,偶数长度的回文子数组的数量为$$$0$$$。
- $$$p_4 = [2, 3, 1]$$$, $$$b_{p_4} = [3, 1, 2, 1, 2, 3, 1]$$$,偶数长度的回文子数组的数量为$$$0$$$。
- $$$p_5 = [3, 1, 2]$$$, $$$b_{p_5} = [3, 1, 2, 1, 3, 1, 2]$$$,偶数长度的回文子数组的数量为$$$0$$$。
- $$$p_6 = [3, 2, 1]$$$, $$$b_{p_6} = [3, 1, 2, 1, 3, 2, 1]$$$,偶数长度的回文子数组的数量为$$$0$$$。
因此,对于所有 $$$i \gt 2$$$,我们有 $$$f(0) = 4$$$、$$$f(1) = 1$$$、$$$f(2) = 1$$$ 和 $$$f(i) = 0$$$。因此,答案是$$$4^1 + 1^2 + 1^3 = 6$$$。