CF1227F1 Wrong Answer on test 233 (Easy Version)

你的程序又出错了。这一次它在第 233 个测试点上得到了“答案错误”。 这是这个问题的简单版本。在本版本中，$1 \le n \le 2000$。只有在你解决并锁定了两个问题后，才能对本题进行 Hack。 本题描述如下：有一份包含 $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$ 取模。

对于第一个样例，满足条件的答案序列有 $[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]$。 由 ChatGPT 4.1 翻译