Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F2. Wrong Answer on test 233 (Hard Version)

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYour 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.

Input

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

Output one integer: the number of answers suits satisfying the given condition, modulo $$$998\,244\,353$$$.

Examples

Input

3 3 1 3 1

Output

9

Input

5 5 1 1 4 2 2

Output

1000

Input

6 2 1 1 2 2 1 1

Output

16

Note

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/09/2020 09:59:24 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|