ストーリー

戦いの中、不思議と冴えた頭で思い出すのは昔のこと。

今からすれば他愛のない、単純な石取りゲームで打ち負かされ、泣いていた僕。その目の前に現れた、ヒーローのようなヒロイン。 それが僕にとっての憧れ、そして、彼女の隣にいたいという気持ちの芽生えだ。

問題文

次のようなゲームを考えます。

• 初期盤面として N 個の机があり、それぞれにりんごが 0 個以上 K 個以下乗っている。
• あなたから初めて、2 人は交互に次の行動をし、先にできなくなった方が負け。
  • 机を 1 つ選んで、それに乗っているりんごを 1 つ以上食べる。

2 人とも最善を尽くしたときにあなたが勝つような初期盤面は何通りあるでしょうか。答えは非常に大きくなる可能性があるため、 10^9+7 で割った余りを答えてください。

制約

• 入力はすべて整数
• 1 \leq N \leq 2000
• 0 \leq K \leq 10^{18}

入力例 1

3 2

出力例 1

20

N=3,K=2 のとき、条件を満たす初期盤面は次の 20 通りです。

(0,0,1), (0,0,2), (0,1,0), (0,1,2), (0,2,0), \\(0,2,1), (1,0,0), (1,0,2), (1,1,1), (1,1,2), \\(1,2,0), (1,2,1), (1,2,2), (2,0,0), (2,0,1), \\(2,1,0), (2,1,1), (2,1,2), (2,2,1), (2,2,2)

入力例 2

2 99

出力例 2

9900

入力例 3

3 5

出力例 3

188

N=3, K=5 のとき、条件を満たす初期盤面は 188 通りあります。

入力例 4

7 20

出力例 4

744195543

解説

解説