故事

在战斗中，我用奇妙而敏锐的头脑回忆起过去的事情。

从现在的角度来看，那只是一个无聊的、简单的石头游戏，我被打败了，哭泣着。在我的眼前出现了一个像英雄一样的女主角。对我来说，她是我向往的对象，我萌生了想要和她在一起的心情。

问题描述

考虑以下游戏：

• 初始状态为有 $N$ 张桌子，每张桌子上放着 $0$ 到 $K$ 个苹果。
• 你先开始，两个人轮流进行下一步行动，先不能行动的人输。
  • 选择一张桌子，吃掉上面的至少一个苹果。

当两个人都采取最佳策略时，有多少种初始状态可以让你赢得比赛？由于答案可能非常大，所以请输出除以 $10^9+7$ 的余数作为答案。

约束条件

• 所有输入都为整数
• $1 \leq N \leq 2000$
• $0 \leq K \leq 10^{18}$

输入

输入以以下格式从标准输入中给出。

$N$ $K$

输出

请输出满足条件的初始状态的数量，以一行形式输出除以 $10^9+7$ 的余数。

示例 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

解释

解释