← 返回题目列表

AtCoder · kupc2013_j

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

有四个选项:

[原图]

入力例 2

2 2 2

出力例 2

2

有两种方法:

[原图]

入力例 3

2 2 3

出力例 3

0

入力例 4

1000000000 1000000000 5

出力例 4

68450176