← 返回题目列表

AtCoder · ddcc2020_qual_f

F. 星际圆盘

中文机器翻译题面 查看原题

分数: 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