Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a matrix $A$ with size $M \times N$. He wants to fill each of its cells with a random integer between $1$ and $K$ (inclusive); these integers are independent.

Then, Chef builds a directed graph on this matrix: for each ordered pair of side-adjacent cells of the matrix such that the value in the first cell is greater than or equal to the value in the second cell, he adds an edge from the first cell to the second cell.

Find the expected value of the number of strongly connected components (SCC) in this graph. It can be proved that the answer can be represented as a fraction $P/Q$, where $P$ and $Q$ are positive integers and $Q$ is coprime with $998,244,353$. You should compute $P \cdot Q^{-1}$ modulo $998,244,353$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $998,244,353$.

------ Input ------
The first and only line of the input contains three space-separated integers $M$, $N$ and $K$.

------ Output ------
Print a single line containing one integer $P \cdot Q^{-1}$ modulo $998,244,353$.

------ Constraints ------
$1 ≤ M ≤ 2$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{8}$

------ Subtasks ------
Subtask #1 (5 points, time limit 1s):
$N ≤ 4$
$K ≤ 5$

Subtask #2 (10 points, time limit 2s): $M = 1$

Subtask #3 (10 points, time limit 2s):
$M = 2$
$N ≤ 500$
$K ≤ 500$

Subtask #4 (75 points, time limit 3s): original constraints

----- Sample Input 1 ------
2 2 2
----- Sample Output 1 ------
873463811
----- explanation 1 ------
The total number of ways to fill the matrix is $16$. We get:
- $1$ SCC with a probability $2/16$
- $2$ SCCs with a probability $12/16$
- $3$ SCCs with a probability $0/16$
- $4$ SCCs with a probability $2/16$

The expected number of SCCs is $2/16 + 24/16 + 8/16 = 34/16 = 34 \cdot 16^{-1} = 873463811$. We can check that indeed, $873463811 \cdot 16 = 34$ modulo $998244353$.

见题面

见题面