AT_ddcc2020_qual_f DISCOSMOS

[problemUrl]: https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_f $ 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 $ で割った余りを求めてください．

入力は以下の形式で標準入力から与えられます． > $ H $ $ W $ $ T $

条件を満たすロボットの設置方法の数を $ 10^9\ +\ 7 $ で割った余りを出力してください．

### 制約 - $ 1\ \leq\ H\ \leq\ 10^9 $ - $ 1\ \leq\ W\ \leq\ 10^9 $ - $ 1\ \leq\ T\ \leq\ 10^9 $ - $ H,\ W,\ T $ はすべて整数 ### Sample Explanation 1 停止型を `.`，右移動型を `>`，下移動型を `v` として，例えば次のような設定方法が条件を満たします． ``` >> .. vv .. .. vv ```