F2. Неправильный ответ на тесте 233 (усложненная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Ваша программа снова не работает, на этот раз она получает вердикт «Неправильный ответ на тесте 233»

Это усложненная версия задачи, в этой версии $$$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$$$.

Примеры
Входные данные
3 3
1 3 1
Выходные данные
9
Входные данные
5 5
1 1 4 2 2
Выходные данные
1000
Входные данные
6 2
1 1 2 2 1 1
Выходные данные
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]$$$.