配点 : 700 点
故事
在战斗中,我头脑异常清晰地回忆起过去。
我哭了,因为我在一个简单的捡石头游戏中被打败了,从现在起这似乎毫无意义了。一个如同英雄一样的女英雄出现在他的眼前。 这就是我所钦佩的,也是我渴望和她在一起的开始。
問題文
考虑以下游戏。
- 作为初始板 有 N 桌子,每张桌子上都有一个苹果。 我的骑行次数少于 0 個以上 K 。
- 第一次来,2 人们轮流采取下一步行动,不能先采取行动的人就输了。
- 办公桌 1 选择一个并摘下上面的苹果。 1 吃多个。
2 有多少早期棋盘是你在其他人都尽力而为时获胜的?答案可能非常大,所以 请回答除以 10^9+7 后的余数。
制約
- 输入全部为整数
- 1 \leq N \leq 2000
- 0 \leq K \leq 10^{18}
入力
输入如下格式从标准输入给出。
N K
出力
计算满足条件的初始棋盘面数。 请在 10^9+7 取模之后的余数 1 行输出。
入力例 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
解説
strong>比赛结束后,将在此处添加该问题的个人解释链接。 </strong> 解説