#DDCC2020QUALF. DISCOSMOS

DISCOSMOS

Score: 900900 points

Problem Statement

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

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

At time 00, 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)(i, j) at time tt, it will be in (i,j+1)(i, j+1) at time t+1t+1. If it is in (i,W)(i, W) at time tt, however, it will be instead in (i,1)(i, 1) at time t+1t+1. (The robots do not collide with each other.)
  • Type-D: If a robot of this type is in (i,j)(i, j) at time tt, it will be in (i+1,j)(i+1, j) at time t+1t+1. If it is in (H,j)(H, j) at time tt, however, it will be instead in (1,j)(1, j) at time t+1t+1.

There are 3H×W3^{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,4T0, T, 2T, 3T, 4T, and all subsequent multiples of TT?

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

Constraints

  • 1H1091 \leq H \leq 10^9
  • 1W1091 \leq W \leq 10^9
  • 1T1091 \leq T \leq 10^9
  • H,W,TH, W, T are all integers.

Input

Input is given from Standard Input in the following format:

HH WW TT

Output

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

2 2 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
869 120 1001
672919729