Problem Description

In the year 2937, DISCO celebrates its 1000th anniversary by creating a new universe called "DISCOSMOS".

DISCOSMOS is represented by a grid of $H \times W$ cells. The cell at the $ i $-th row from the top and the $ j $-th column from the left is denoted as $ (i, j) $ $(1 \leq i \leq H, 1 \leq j \leq W)$.

At time $ 0 $, a robot is placed on each cell. Each robot is one of the following three types:

• Stop type: Always remains stationary.
• Right move type: If it is at $ (i, j) $ at time $ t $, it will be at $ (i, j+1) $ at time $ t+1 $. However, if it is at $ (i, W) $ at time $ t $, it will be at $ (i, 1) $ at time $ t+1 $. (Robots do not collide with each other.)
• Down move type: If it is at $ (i, j) $ at time $ t $, it will be at $ (i+1, j) $ at time $ t+1 $. However, if it is at $ (H, j) $ at time $ t $, it will be at $ (1, j) $ at time $ t+1 $.

There are $3^{H \times W}$ possible ways to place these robots. Among them, how many ways ensure that at any time $0, T, 2T, 3T, 4T, \dots$, there is exactly one robot in each cell?

Since the answer can be very large, output it modulo $ 10^9 + 7 $.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ T $

Output Format

Output the number of valid robot placements modulo $ 10^9 + 7 $.

Sample Input and Output

Sample Input #1

2 2 1

Sample Output #1

9

Sample Input #2

869 120 1001

Sample Output #2

672919729

Notes/Hints

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

Sample Explanation 1

Using . for stop type, > for right move type, and v for down move type, for example, the following setup satisfies the condition:

>>
..
vv
..
..
vv

见题面 Input 部分

见题面 Output 部分