057 - Domino Tiling Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

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