← 返回题目列表

AtCoder · math_and_algorithm_aw

057. 多米诺骨牌平铺

中文机器翻译题面 查看原题

配点 : 1000 点

問題文

K \times N 矩形网格,1 \times 2 或 至少 2 \times 1 完全填充矩形图块的方法数量 除以 1000000007 (=10^9+7) 求余数。然而,正确的敷设方法是满足以下条件的敷设方法。

  • 瓷砖不得超出网格,并且不同的瓷砖不得重叠。
  • 所有图块都完全位于网格上。 2 完全覆盖正方形。

此外,由于旋转或翻转而导致的匹配铺设方法也被视为不同。

制約

  • 2 \le K \le 4
  • 5 \le N \le 10^{18}
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

K N

出力

请打印答案。 到达

部分点

在这个问题中,初始分数是 0 在以下条件下将增加积分。 如果您对所有满足

  • K=2 的情况都回答正确, 2 积分已添加。
  • K=3 的情况都回答正确, 30 积分已添加。
  • K=4 的情况都回答正确, 400 积分已添加。
  • 如果所有案例都回答正确, 568 积分已添加。
    • 最终的满分是 请解决 1000 点。

入力例 1

2 6

出力例 1

13

入力例 2

3 8

出力例 2

153

入力例 3

4 7

出力例 3

781