{"problem":{"name":"DISCOSMOS","description":{"content":"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)$ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ddcc2020_qual_f"},"statements":[{"statement_type":"Markdown","content":"In $2937$, DISCO creates a new universe called DISCOSMOS to celebrate its $1000$\\-th anniversary.\nDISCOSMOS 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.\nAt time $0$, one robot will be placed onto each square. Each robot is one of the following three types:\n\n*   Type-H: Does not move at all.\n*   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.)\n*   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$.\n\nThere 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$?\nSince the count can be enormous, compute it modulo $(10^9 + 7)$.\n\n## Constraints\n\n*   $1 \\leq H \\leq 10^9$\n*   $1 \\leq W \\leq 10^9$\n*   $1 \\leq T \\leq 10^9$\n*   $H, W, T$ are all integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ddcc2020_qual_f","tags":[],"sample_group":[["2 2 1","9\n\nShown 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:\n\n\\>>  ..  vv\n..  ..  vv"],["869 120 1001","672919729"]],"created_at":"2026-03-03 11:01:13"}}