尺寸 沿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
有四个选项:
[原图]
入力例 2
2 2 2
出力例 2
2
有两种方法:
[原图]
入力例 3
2 2 3
出力例 3
0
入力例 4
1000000000 1000000000 5
出力例 4
68450176