Ваша программа снова не работает, на этот раз она получает вердикт «Неправильный ответ на тесте 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]\) удовлетворяет условию и должен быть посчитан.
Примечание
На первый пример, корректные наборы ответов — это \([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]\).