AT_ddcc2020_qual_f.DISCOSMOS

2937 年，DISCO 为了纪念创业 1000 周年，创造了一个新的宇宙“DISCOSMOS”！

DISCOSMOS 是一个 $H \times W$ 的格子宇宙。自上而下第 $i$ 行，自左而右第 $j$ 列的格子用 $(i, j)$ 表示（$1 \leq i \leq H,\ 1 \leq j \leq W$）。

在时刻 $0$，每个格子上都放置了一台机器人。每台机器人有以下三种类型之一：

• 停止型：始终静止不动。
• 右移型：如果在时刻 $t$ 处于 $(i, j)$，则在时刻 $t+1$ 处于 $(i, j+1)$。但如果在时刻 $t$ 处于 $(i, W)$，则在时刻 $t+1$ 处于 $(i, 1)$。（机器人之间不会发生碰撞。）
• 下移型：如果在时刻 $t$ 处于 $(i, j)$，则在时刻 $t+1$ 处于 $(i+1, j)$。但如果在时刻 $t$ 处于 $(H, j)$，则在时刻 $t+1$ 处于 $(1, j)$。

这样的机器人放置方式共有 $3^{H \times W}$ 种。在这些放置方式中，有多少种能够满足：在时刻 $0, T, 2T, 3T, 4T, \dots$ 的每一个时刻，所有格子上都恰好有一台机器人？

请注意，答案可能非常大，请输出对 $10^9 + 7$ 取模的结果。

输入从标准输入中给出，格式如下：

$H$ $W$ $T$

输出满足条件的机器人放置方式数对 $10^9 + 7$ 取模的结果。

限制条件

• $1 \leq H \leq 10^9$
• $1 \leq W \leq 10^9$
• $1 \leq T \leq 10^9$
• $H, W, T$ 均为整数

样例解释 1

用停止型表示为 .，右移型为 >，下移型为 v，例如如下的放置方式满足条件：

>>  ..  vv
..  ..  vv

由 ChatGPT 4.1 翻译