时空限制

1S/512M

题目描述

给定一个 $n \times m$ 的网格，你需要为其中的每一个格子都染上一种颜色。可用的颜色共有 $k$ 种，我们将其编号为 $1, 2, \ldots, k$。

染色时必须遵守一条特殊规则：颜色 $1$ 非常“特殊”，任意两个被染成颜色 $1$ 的格子都不能有公共边（即它们不能在上下左右四个方向上直接相邻）。

求在所有符合规则的染色方案中，颜色为 $1$ 的格子一共出现了多少次？

由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

格式

输入格式

输入一行，包含三个整数 $n, m, k$。

输出格式

输出一个整数，表示所有合法染色方案中颜色为 $1$ 的格子总数，对 $998244353$ 取模。

样例

样例输入 #1

2 2 2

样例输出 #1

8

样例解释 #1

以下是满足条件的所有染色情况，其中黑色表示颜色 $1$，白色表示颜色 $2$。

故颜色 $1$ 出现的总个数为 $1 + 2 + 1 + 2 + 1 + 1 = 8$。

样例输入 #2

4 10 20

样例输出 #2

791797194

数据规模

对于 $20\%$ 的数据，$1 \leq n \times m \leq 20$。

对于 $40\%$ 的数据，$1 \leq n \leq 5$，$1 \leq m \leq 1000$。

对于 $60\%$ 的数据，$1 \leq n \leq 5$，$1 \leq m \leq 10^9$。

对于 $100\%$ 的数据，$1 \leq n \leq 8$，$1 \leq m \leq 10^9$, $2 \leq k \leq 10^9$。