CF1227F1.Wrong Answer on test 233 (Easy Version)

Your program fails again. This time it gets "Wrong answer on test 233"

.

This is the easier version of the problem. In this version $1 \le n \le 2000$. You can hack this problem only if you solve and lock both problems.

The problem is about a test containing $n$ one-choice-questions. Each of the questions contains $k$ options, and only one of them is correct. The answer to the $i$-th question is $h_{i}$, and if your answer of the question $i$ is $h_{i}$, you earn $1$ point, otherwise, you earn $0$ points for this question. The values $h_1, h_2, \dots, h_n$ are known to you in this problem.

However, you have a mistake in your program. It moves the answer clockwise! Consider all the $n$ answers are written in a circle. Due to the mistake in your program, they are shifted by one cyclically.

Formally, the mistake moves the answer for the question $i$ to the question $i \bmod n + 1$. So it moves the answer for the question $1$ to question $2$, the answer for the question $2$ to the question $3$, ..., the answer for the question $n$ to the question $1$.

We call all the $n$ answers together an answer suit. There are $k^n$ possible answer suits in total.

You're wondering, how many answer suits satisfy the following condition: after moving clockwise by $1$, the total number of points of the new answer suit is strictly larger than the number of points of the old one. You need to find the answer modulo $998\,244\,353$.

For example, if $n = 5$, and your answer suit is $a=[1,2,3,4,5]$, it will submitted as $a'=[5,1,2,3,4]$ because of a mistake. If the correct answer suit is $h=[5,2,2,3,4]$, the answer suit $a$ earns $1$ point and the answer suite $a'$ earns $4$ points. Since $4 \gt 1$, the answer suit $a=[1,2,3,4,5]$ should be counted.

你的程序再次出错。这次报错为“测试 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$ 种可能的答题方案。

你现在想知道：有多少种答题方案满足如下条件——将其顺时针移动一位后，新答题方案的总得分严格大于原答题方案的总得分？你需要输出答案对 $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]$ 应被计入。

The first line contains two integers $n$, $k$ ($1 \le n \le 2000$, $1 \le k \le 10^9$) — the number of questions and the number of possible answers to each question.

The following line contains $n$ integers $h_1, h_2, \dots, h_n$, ($1 \le h_{i} \le k)$ — answers to the questions.

第一行包含两个整数 $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$）—— 表示各问题的答案。

Output one integer: the number of answers suits satisfying the given condition, modulo $998\,244\,353$.

输出一个整数：满足给定条件的答案个数，对 $998\,244\,353$ 取模。

For the first example, valid answer suits are $[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]$.

对于第一个样例，合法的答案组合有 $[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]$。