No.377 背景パターン

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 18
作問者 : EmKjpEmKjp / テスター : 紙ぺーぱー紙ぺーぱー

3 ProblemId : 561 / 出題時の順位表

問題文

高さ $H$、幅 $W$ の画像を作成して、それを上下左右に繰り返し並べることで無限に広がる背景パターンを作成することにしました。
色は $0$ から $K-1$ までの $K$ 色があり、画像の$W \times H$個の各ピクセルには $K$ 色のうち 1 色が入ります。

例えば、高さ 2 、幅 3 の画像

123
456
を繰り返し並べることで得られる背景パターンは以下のようになります。
123123123123123123
456456456456456456
123123123123123123
456456456456456456
123123123123123123
456456456456456456
(無限に同じパターンが続きます)
高さ $H$、幅 $W$ の画像から生成できる背景パターンの個数を $10^9 + 7$ で割った余りを出力するプログラムを書いてください。
ただし平行移動すると全く同じになるような背景パターンは同一のものと見なします。
例えば以下の6つの画像から得られる背景パターンは全て同じものとして扱われます。
123 231 312 456 564 645
456 564 645 123 231 312

入力

H W K

$1 \le H \le 10^9 $
$1 \le W \le 10^9 $
$1 \le K \le 10^9 $

出力

生成できる背景パターンのパターン数を $10^9 + 7$ で割った余りを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2 2 1
出力
1

1色しか使えないので全面1色の背景画像しか作れません。

サンプル2
入力
2 2 2
出力
7

生成できる背景パターンは以下の 7 通りです。

111111 101010 111111 101010 111111 101010 000000
111111 010101 010101 000000 000000 101010 000000
111111 101010 111111 101010 111111 101010 000000
111111 010101 010101 000000 000000 101010 000000
111111 101010 111111 101010 111111 101010 000000

サンプル3
入力
1 3 3
出力
11

生成できる背景パターンは以下の 11 通りです。

000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021
000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021
000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021
000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021
000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021

サンプル4
入力
5 7 10
出力
878302877

サンプル5
入力
111 222 333
出力
91610936

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。