← 返回题目列表

Codeforces · 1227/F1

F1. 测试 233 的错误答案(简单版)

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

这是问题的简单版本。在此版本中$$$1 \le n \le 2000$$$。只有解决并锁定这两个问题,你才能解决这个问题。

问题是关于包含 $$$n$$$ 单选题的测试。每道题都包含 $$$k$$$ 个选项,并且只有一个选项是正确的。第 $$$i$$$ 问题的答案是 $$$h_{i}$$$,如果您对问题 $$$i$$$ 的答案是 $$$h_{i}$$$,您将获得 $$$1$$$ 分,否则,您将获得 $$$0$$$ 分。在这个问题中,值 $$$h_1, h_2, \dots, h_n$$$ 是已知的。

但是,您的程序有一个错误。它顺时针移动答案!考虑所有 $$$n$$$ 答案都写在一个圆圈中。由于你的程序错误,它们循环移动一位。

正式而言,该错误将问题 $$$i$$$ 的答案移至问题 $$$i \bmod n + 1$$$。因此,它将问题 $$$1$$$ 的答案移至问题 $$$2$$$,将问题 $$$2$$$ 的答案移至问题 $$$3$$$,...,将问题 $$$n$$$ 的答案移至问题 $$$1$$$。

我们将所有 $$$n$$$ 答案一起称为答案套装。总共有 $$$k^n$$$ 种可能的答案。

你想知道,有多少个答案花色满足以下条件:顺时针移动$$$1$$$后,新答案花色的总点数严格大于旧答案花色的点数。您需要找到对 $$$998\,244\,353$$$ 取模的答案。

例如,如果$$$n = 5$$$,而您的答案花色是$$$a=[1,2,3,4,5]$$$,则由于错误,它将提交为$$$a'=[5,1,2,3,4]$$$。如果正确答案花色是 $$$h=[5,2,2,3,4]$$$,则答案花色 $$$a$$$ 获得 $$$1$$$ 分,答案花色 $$$a'$$$ 获得 $$$4$$$ 分。由于 $$$4 > 1$$$,所以答案花色 $$$a=[1,2,3,4,5]$$$ 应该被计算在内。

输入

第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1 \le n \le 2000$$$, $$$1 \le k \le 10^9$$$) — 问题数量以及每个问题的可能答案数量。

以下行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$, ($$$1 \le h_{i} \le k)$$$ - 问题的答案。

输出

输出一个整数:满足给定条件的答案数,以$$$998\,244\,353$$$为模。

示例

输入 #1

3 3
1 3 1

输出 #1

9

输入 #2

5 5
1 1 4 2 2

输出 #2

1000

注意

对于第一个示例,有效答案花色为 $$$[2,1,1]、[2,1,2]、[2,1,3]、[3,1,1]、[3,1,2]、[3,1,3]、[3,2,1]、[3,2,2]、[3,2,3]$$$。