这是问题的更难版本。在此版本中,$$$1 \le n \le 2\cdot10^5$$$。如果你锁定了这个问题,你就可以解决这个问题。但只有当你锁定了这两个问题时,你才能破解前一个问题。
问题是完成$$$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 2\cdot10^5$$$, $$$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
输入 #3
6 2 1 1 2 2 1 1
输出 #3
16
注意
对于第一个示例,有效答案花色为 $$$[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]$$$。