配点 : 900 点
問題文
长度 N 整数序列 A=(A_1,A_2,\cdots,A_N) 和整数 给出了 K 。
你 A 的副本 K 排列并连接它们,长度 我得到了 NK 整数序列 x=(x_1,x_2,\cdots,x_{NK}) 。
您现在可以执行以下操作 执行 1 次。 选择
- x 的一个(不一定连续)(可以为空)子序列,并以相反的顺序重新排列其元素。 更准确地说,索引的顺序 1 \leq i_1<i_2<\cdots<i_s \leq NK (列长度 s 也是可选的),并且每个 1 \leq j \leq s 分区 if x_{i_j} 的值 替换为 x_{i_{s-j+1}} 。 所有这些替换都是同时发生的。
操作后 x 可能的序列数为 除以 998244353 后求余数。
制約
- 1 \leq N \leq 300
- 1 \leq K \leq 10^{18}
- 1 \leq A_i \leq N
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \cdots A_N
出力
打印答案。
入力例 1
2 2 1 2
出力例 1
6
在此示例中,x=(1,2,1,2) 。 手术后 x 可能的顺序如下: 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) 。
入力例 2
3 2 3 3 3
出力例 2
1
入力例 3
5 3 1 2 3 4 5
出力例 3
9216
入力例 4
30 1000000000000 8 3 8 10 1 5 3 1 6 4 3 6 2 6 6 9 5 5 8 3 3 4 10 2 3 2 8 10 8 1
出力例 4
401626004