问题描述

在 $2937$ 年，DISCO 创建了一个名为 DISCOSMOS 的新宇宙，以庆祝其第 $1000$ 个周年。

DISCOSMOS 可以被描述为一个 $H \times W$ 网格。用 $(i, j)$ 表示从上到下的第 $i$ 行和从左到右的第 $j$ 列的方块。

在时间 $0$，每个方块上都会放置一个机器人。每个机器人属于以下三种类型之一：

• H 类型：完全不移动。
• R 类型：如果一个 R 类型机器人在时间 $t$ 位于 $(i, j)$，那么它在时间 $t+1$ 将位于 $(i, j+1)$。但是如果在时间 $t$ 它位于 $(i, W)$，那么在时间 $t+1$ 会出现在 $(i, 1)$。（机器人之间不会发生碰撞）
• D 类型：如果一个 D 类型机器人在时间 $t$ 位于 $(i, j)$，那么它在时间 $t+1$ 将位于 $(i+1, j)$。但是如果在时间 $t$ 它位于 $(H, j)$，那么在时间 $t+1$ 会出现在 $(1, j)$。

总共有 $3^{H \times W}$ 种方式可以放置这些机器人。其中多少种方式使得在时间 $0, T, 2T, 3T, 4T$ 及其之后的倍数时刻每个方块都被一个机器人占据？

由于计数可能非常大，要求以模 $(10^9 + 7)$ 的形式进行计算。

约束条件

• $1 \leq H \leq 10^9$
• $1 \leq W \leq 10^9$
• $1 \leq T \leq 10^9$
• $H, W, T$ 都是整数。

输入输出格式

首先，从标准输入中接收以下格式的输入：

$H$ $W$ $T$

然后，打印满足条件的放置机器人方式的数量，以模 $(10^9 + 7)$ 的形式。

示例 输入输出

输入示例 1

2 2 1

输出示例 1

9

一些满足条件的放置机器人方式如下所示，其中.、> 和 v 分别表示 H 类型、R 类型和 D 类型的机器人：

>>  ..  vv
..  ..  vv

输入示例 2

869 120 1001

输出示例 2

672919729