J - タイル置き
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 128 MB
サイズ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