#896 Colorful Domino Tiling

Statement

Statement language

There is a grid with $N$ rows and $M$ columns and an unlimited supply of dominoes in each of $K$ distinct colors. A domino covers two cells sharing a side and may be placed horizontally or vertically.

Cover every cell without overlap and without extending outside the grid. If any cell covered by one domino shares a side with a cell covered by another domino, those two dominoes must have different colors. Meeting only at a corner imposes no restriction.

Count the ways to choose both the domino placement and the color of every domino, modulo $998\,244\,353$ . You need not use all $K$ colors. Two ways are different if their placements differ or if any domino in the same position has a different color. Rotations and reflections are counted separately whenever they change the placement or colors on the original grid. Dominoes of the same color are indistinguishable.

Input

The input is given in the following format:

$N\ M\ K$

Output

Print the number of valid ways modulo $998\,244\,353$ . If there is no valid way, print $\tt{0}$ .

Constraints

$1\leq N,M\leq8$ .
$4\leq K\leq100$ .
All input values are integers.

Subtasks

#	Score	Constraints
1	25	$NM\leq16$ .
2	75	No additional constraints.

Samples

Sample 1

Input

2 2 4

Output

24

The grid can be covered by two horizontal dominoes or two vertical dominoes. In either placement, the dominoes are adjacent and must use different colors. Thus there are $2\cdot4\cdot3=24$ ways.

Sample 2

Input

3 3 5

Output

0

Nine cells cannot be completely covered by dominoes of two cells each.