F - DISCOSMOS Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 900 点

問題文

2937 年，DISCO は創業 1000 年を記念して新たな宇宙「DISCOSMOS」を作りました！

DISCOSMOS は H \times W のマス目で表される宇宙です．上から i 番目，左から j 番目のマスを (i, j) (1 \leq i \leq H, 1 \leq j \leq W) で表します．

時刻 0 に，各マスにロボットが 1 台ずつ設置されます．各ロボットは以下の 3 種類のいずれかです．

  • 停止型：常に停止している．
  • 右移動型：時刻 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 のいずれにおいても，全てのマスにロボットが 1 台ずつ存在するような設置方法は何通りあるでしょうか？

ただし，答えは非常に大きくなる場合があるので，代わりにこれを 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 として，例えば次のような設定方法が条件を満たします． 

>>  ..  vv
..  ..  vv

入力例 2

869 120 1001

出力例 2

672919729

Score: 900 points

Problem Statement

In 2937, DISCO creates a new universe called DISCOSMOS to celebrate its 1000-th anniversary.

DISCOSMOS can be described as an H \times W grid. Let (i, j) (1 \leq i \leq H, 1 \leq j \leq W) denote the square at the i-th row from the top and the j-th column from the left.

At time 0, one robot will be placed onto each square. Each robot is one of the following three types:

  • Type-H: Does not move at all.
  • Type-R: If a robot of this type is in (i, j) at time t, it will be in (i, j+1) at time t+1. If it is in (i, W) at time t, however, it will be instead in (i, 1) at time t+1. (The robots do not collide with each other.)
  • Type-D: If a robot of this type is in (i, j) at time t, it will be in (i+1, j) at time t+1. If it is in (H, j) at time t, however, it will be instead in (1, j) at time t+1.

There are 3^{H \times W} possible ways to place these robots. In how many of them will every square be occupied by one robot at times 0, T, 2T, 3T, 4T, and all subsequent multiples of T?

Since the count can be enormous, compute it modulo (10^9 + 7).

Constraints

  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 1 \leq T \leq 10^9
  • H, W, T are all integers.

Input

Input is given from Standard Input in the following format:

H W T

Output

Print the number of ways to place the robots that satisfy the condition, modulo (10^9 + 7).

Sample Input 1

2 2 1

Sample Output 1

9

Shown below are some of the ways to place the robots that satisfy the condition, where ., >, and v stand for Type-H, Type-R, and Type-D, respectively:

>>  ..  vv
..  ..  vv

Sample Input 2

869 120 1001

Sample Output 2

672919729