AT_jsc2024_final_c.Subsequence Reversal

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$ 和一个整数 $K$。

你将 $A$ 的副本并列 $K$ 次连接，得到一个长度为 $NK$ 的整数序列 $x=(x_1,x_2,\cdots,x_{NK})$。

接下来你将恰好进行下面的操作一次：

• 选择 $x$ 的一个（不一定连续的）（可以为空）子序列，并将其元素顺序翻转。更准确地说，选择一个下标序列 $1 \leq i_1 < i_2 < \cdots < i_s \leq NK$（长度 $s$ 任意），并且对于每一个 $1 \leq j \leq s$，用 $x_{i_{s-j+1}}$ 的值替换 $x_{i_j}$。这些置换是同时进行的。

请你求出操作后可能得到的数列 $x$ 有多少种，结果对 $998244353$ 取模。

输入为以下格式，从标准输入读入：

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

输出答案。

样例解释 1

在本例中，$x=(1,2,1,2)$。操作后可能得到的数列有以下 $6$ 种：

• $(1,2,1,2)$：$s=1$，选择 $(i_1)=(1)$ 即可。
• $(2,1,1,2)$：$s=2$，选择 $(i_1,i_2)=(1,2)$ 即可。
• $(1,1,2,2)$：$s=2$，选择 $(i_1,i_2)=(2,3)$ 即可。
• $(1,2,2,1)$：$s=2$，选择 $(i_1,i_2)=(3,4)$ 即可。
• $(2,2,1,1)$：$s=2$，选择 $(i_1,i_2)=(1,4)$ 即可。
• $(2,1,2,1)$：$s=4$，选择 $(i_1,i_2,i_3,i_4)=(1,2,3,4)$ 即可。

数据范围

• $1 \leq N \leq 300$
• $1 \leq K \leq 10^{18}$
• $1 \leq A_i \leq N$
• 输入的所有数都是整数。

由 ChatGPT 5 翻译