Grammy 正在 Pigeland 城市公园享受她的假期。她对公园里的地砖产生了兴趣。经过仔细观察，她发现每一块地砖都是一个 $W \times H$ 的矩形网格，上面有垂直和/或水平的彩色线段。这些彩色线段的端点位于网格点上，并将矩形恰好分割成 $k$ 个子矩形。

例如，下图展示了一块 $W = 9, H = 5, k = 4$ 的地砖。

Grammy 想知道满足条件的不同地砖的数量。请告诉她答案。由于答案可能非常大，你需要输出答案对 $998\,244\,353$ 取模的结果。

注意，当且仅当一个网格线在其中一块地砖中被涂色而在另一块中未被涂色时，这两块地砖才被视为不同。如果两块地砖可以通过旋转或翻转变为相同，它们仍可能被视为不同的地砖。

输入格式

仅一行，包含三个整数 $W, H, k$ ($1 \le W, H \le 10^9, 1 \le k \le \min(5, W \cdot H)$)。

输出格式

输出一个整数，表示满足条件的不同地砖的数量对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

2 3 5

样例输出 1

7

样例输入 2

4 3 5

样例输出 2

307

样例输入 3

6 372065168 5

样例输出 3

114514