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 .. vv ``` 由 ChatGPT 4.1 翻译