← 返回题目列表

AtCoder · jsc2024_final_c

C. 后续反转

中文机器翻译题面 查看原题

配点 : 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