Tile Setting

Time Limit : 2 sec, Memory Limit : 131072 KB

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

Source: Kyoto University Programming Contest 2013 , Kyoto, Japan, 2013-07-06
http://www.kupc.jp/
http://kupc2013.contest.atcoder.jp/