Problem Description

Consider the following game:

• The initial board has $ N $ tables, each with $ 0 $ to $ K $ apples on it.
• Starting with you, two players take turns performing the following action, and the one who cannot act anymore loses.
• Choose one table and eat one or more apples on it.

How many initial board configurations are there such that you win when both players play optimally? Since the answer can be very large, output it modulo $ 10^9+7 $.

Input Format

The input is given from standard input in the following format:

$ N $ $ K $

Output Format

Output the number of initial board configurations that satisfy the condition, modulo $ 10^9+7 $, in one line.

Sample Input and Output

Sample Input #1

3 2

Sample Output #1

20

Sample Input #2

2 99

Sample Output #2

9900

Sample Input #3

3 5

Sample Output #3

188

Sample Input #4

7 20

Sample Output #4

744195543

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 2000$
• $0 \leq K \leq 10^{18}$

Sample Explanation 1

For $ N=3, K=2 $, the initial board configurations that satisfy the condition are the following $ 20 $ cases: $(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

For $ N=3, K=5 $, there are $ 188 $ initial board configurations that satisfy the condition.

见题面 Input 部分

见题面 Output 部分