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