Problem Description

Consider the following game:

• Prepare $N$ squares arranged in a row and a large number of stones.
• Initially, place $a_i$ stones in square $i\ (1 \leq i \leq N)$.
• A player can perform the following operation any number of times: "Choose a square $i$ that contains exactly $i$ stones, discard all stones in that square, and add one stone to each of the squares from $1$ to $i-1$."
• The final score is the total number of stones remaining in the squares.

Let $f(a)$ be the minimum possible score when playing this game with a sequence $a$ of length $N$.

What is the sum of $f(a)$ for all sequences $a$ of length $N$ where each element is between $0$ and $K$ (inclusive)? Since the answer can be very large, output it modulo $1000000007\ (=\ 10^9+7)$.

Input Format

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

$N$ $K$

Output Format

Output the sum of $f(a)$ modulo $1000000007\ (=\ 10^9+7)$.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

10

Sample Input #2

20 17

Sample Output #2

983853488

Notes/Hints

Constraints

• $1 \leq N \leq 100$
• $1 \leq K \leq N$

Sample Explanation 1

There are $9$ possible sequences $a$ of length $2$ where each element is between $0$ and $2$, inclusive. The values of $f(a)$ for each sequence and an example of the operations to achieve them are as follows:

• $f(\{0,0\})$: $0$ (cannot perform any operation)
• $f(\{0,1\})$: $1$ (cannot perform any operation)
• $f(\{0,2\})$: $0$ (perform operations on square $2$ then square $1$)
• $f(\{1,0\})$: $0$ (perform operation on square $1$)
• $f(\{1,1\})$: $1$ (perform operation on square $1$)
• $f(\{1,2\})$: $0$ (perform operations on square $1$, then square $2$, then square $1$)
• $f(\{2,0\})$: $2$ (cannot perform any operation)
• $f(\{2,1\})$: $3$ (cannot perform any operation)
• $f(\{2,2\})$: $3$ (perform operation on square $2$)

见题面 Input 部分

见题面 Output 部分