Wrong Answer on test 233 (Hard Version)

题意翻译

给定 $n$，$k$ 和值域 $[1,k]$ 的 $n$ 个整数 $h_i$，求有多少个长为 $n$ 的整数序列 $a$ 满足值域 $[1,k]$，且 $\sum\limits_{i=1}^n[a_i=h_i]<\sum\limits_{i=1}^n[a_i=h_{(i\bmod{n})+1}]$。

题目描述

Your program fails again. This time it gets "Wrong answer on test 233" .This is the harder version of the problem. In this version, $ 1 \le n \le 2\cdot10^5 $ . You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems. The problem is to finish $ 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 2\cdot10^5 $ , $ 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

输入样例 #3

6 2
1 1 2 2 1 1

输出样例 #3

16

说明

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