Score: 900 points
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:
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).
Input is given from Standard Input in the following format:
H W T
Print the number of ways to place the robots that satisfy the condition, modulo (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