J - タイル置き

サイズH×Wの盤面にサイズ1×2のタイルをマス目にそってN個配置する方法が何通りあるか求めたい.

タイルは重なってはいけない. また縦横どちらの向きに置いても構わない.

タイルは全て同じ見た目であり互いに区別しないものとする.

タイルは180度回転しても同じ見た目であり、区別しないものとする.

答えは大きくなる可能性があるので1,000,000,007で割った余りを答えよ

入力形式

入力は以下の形式で与えられる．

H W N

出力形式

タイルの置き方の総数を 1,000,000,007 で割った余りを出力せよ．

制約

• 1 ≤ H ≤ 1,000,000,000
• 1 ≤ W ≤ 1,000,000,000
• 1 ≤ N ≤ 5
• 入力値はすべて整数である．

この問題の判定には，50 点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• 1 ≤ H ≤ 6
• 1 ≤ W ≤ 6

入出力例

入力例 1

2 2 1

出力例 1

4

次の4通りある。

入力例 2

2 2 2

出力例 2

2

次の2通りある

入力例 3

2 2 3

出力例 3

0

入力例 4

1000000000 1000000000 5

出力例 4

68450176

---