AT_iroha2019_day4_e 芽生え

[problemUrl]: https://atcoder.jp/contests/iroha2019-day4/tasks/iroha2019_day4_e 次のようなゲームを考えます。 - 初期盤面として $ N $ 個の机があり、それぞれにりんごが $ 0 $ 個以上 $ K $ 個以下乗っている。 - あなたから初めて、$ 2 $ 人は交互に次の行動をし、先にできなくなった方が負け。 - 机を $ 1 $ つ選んで、それに乗っているりんごを $ 1 $ つ以上食べる。 $ 2 $ 人とも最善を尽くしたときにあなたが勝つような初期盤面は何通りあるでしょうか。答えは非常に大きくなる可能性があるため、 $ 10^9+7 $ で割った余りを答えてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $

条件を満たす初期盤面の数を $ 10^9+7 $ で割った余りを $ 1 $ 行に出力してください。

### ストーリー 戦いの中、不思議と冴えた頭で思い出すのは昔のこと。 今からすれば他愛のない、単純な石取りゲームで打ち負かされ、泣いていた僕。その目の前に現れた、ヒーローのようなヒロイン。 それが僕にとっての憧れ、そして、彼女の隣にいたいという気持ちの芽生えだ。 ### 制約 - 入力はすべて整数 - $ 1\ \leq\ N\ \leq\ 2000 $ - $ 0\ \leq\ K\ \leq\ 10^{18} $ ### 解説 [解説](https://img.atcoder.jp/iroha2019-day4/editorial-E.pdf) ### Sample Explanation 1 $ 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) $ ### Sample Explanation 3 $ N=3,\ K=5 $ のとき、条件を満たす初期盤面は $ 188 $ 通りあります。