配点: $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$ で割った余りを出力してください．

2 2 1

9

停止型を .，右移動型を >，下移動型を v として，例えば次のような設定方法が条件を満たします．

>>  ..  vv
..  ..  vv

869 120 1001

672919729