E. Metrix
time limit per test
10 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

It's like you are from The Matrix movies...

For any positive integer $$$N$$$, let's consider the $$$N \times N$$$ matrix $$$A$$$, where A_{i,j} = ((j - i) mod N) + 1 for every $$$1 \le i,j \le N$$$.

For example, for $$$N = 4$$$, the matrix is:

$$$\matrix{ 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 }$$$

Given two integers $$$2 \le N \le 10^6$$$ and $$$1 \le K \le 10^6$$$, such that $$$2 \le N \cdot K \le 10^6$$$, find the matrix $$$A' = A^K$$$.

Since the matrix can be huge, given a prime integer $$$2 \le B \lt 998244353$$$ you need to output the following encoding of $$$A'$$$:

$$$\sum_{i=1}^n \sum_{j=1}^n (A_{i, j}' \cdot B^{(N-i) * N + (N - j)}) \mod 998244353$$$

Input

The only line of the input contains 3 integers $$$N, K, B$$$, having the meaning as in the statement.

Output

The output should contain one line, representing the answer modulo $$$\mathbf{998244353}$$$.

Examples
Input
15 19 666013
Output
693191805
Input
2 2 7
Output
1944