题目描述

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

2 2 1

9

869 120 1001

672919729

提示

制約

• $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