分数: 900 点
问题陈述
In 2937,DISCO 创建了一个名为 DISCOSMOS 的新宇宙来庆祝它的诞生 1000周年纪念日。
DISCOSMOS 可以描述为 H \times W 网格。让 (i, j) (1 \leq i \leq H, 1 \leq j \leq W) 表示位于 i从顶部算起的第行和 j左起第 列。
时间 0,每个方格上都会放置一个机器人。每个机器人都是以下三种类型之一:
- H 型:根本不动。
- Type-R:如果该类型的机器人位于 (i, j) 时间 t,它将在 (i, j+1) 时间 t+1。如果是在 (i, W) 时间 t,但是,它将改为 (i, 1) 时间 t+1。 (机器人不会互相碰撞。)
- D 型:如果该类型的机器人位于 (i, j) 时间 t,它将在 (i+1, j) 时间 t+1。如果是在 (H, j) 时间 t,但是,它将改为 (1, j) 时间 t+1.
有 3^{H \times W} 放置这些机器人的可能方法。每个方格有时会被一个机器人占据多少个 0, T, 2T, 3T, 4T,以及所有后续的倍数 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 均为整数。
输入
输入由标准输入按以下格式给出:
H W T
输出
打印满足条件的机器人放置方式的数量,取模 (10^9 + 7).
样本输入 1
2 2 1
示例输出 1
9
满足条件的机器人的一些放置方式如下所示,其中 ., >,和 v 分别代表 Type-H、Type-R 和 Type-D:
>> .. vv .. .. vv
示例输入 2
869 120 1001
示例输出 2
672919729