408524: GYM103181 E Metrix

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:

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

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

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

15 19 666013

693191805

2 2 7

1944