Wrong Answer on test 233 (Easy Version)

题意翻译

你的程序又炸了！这次是 $\textsf{Wrong answer on test 233}$。 这是这个问题的简单版本，在这个问题里 $1 \le n \le 2000$。 有 $n$ 个单选题，每题有 $h$ 个选项，每道题做对得 $1$ 分，否则得 $0$ 分。 你的程序出现了故障，会使所有选项向右移动一题，也就是说第一题的**你提交的**答案会变成第二题你提交的的，第二题会变成第三题的……第 $n$ 题会变成第一题的。 求在所有的 $h^n$ 个可能的作答中，程序故障后得分反而更高的作答方案数。

题目描述

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 > 1 $ , the answer suit $ a=[1,2,3,4,5] $ should be counted.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3 3
1 3 1

输出样例 #1

9

输入样例 #2

5 5
1 1 4 2 2

输出样例 #2

1000

说明

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] $ .