配点 : 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