J. Perfect Chord
time limit per test
2 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Aria, a composer, is trying to create the perfect chord for her orchestra of $$$k$$$ musicians. She wants the chord to contain exactly $$$k$$$ notes, and the sum of the values of each note should be exactly $$$n$$$. Each note is represented by a positive integer indicating its pitch.

In a chord, the order of notes doesn't matter, but the same pitch can be used multiple times (multiple instruments can play the same note). For example, a chord with notes $$$\{1, 3\}$$$ is the same as $$$\{3, 1\}$$$, and a chord with $$$\{2, 2\}$$$ is also valid.

For each valid chord with pitches $$$\{ p_1, p_2, \dots, p_K \}$$$ that sum to $$$n$$$, Aria wants to calculate the harmony level of the chord, which is defined as the sum of the squares of each pitch: $$$$$$ p_1^2 + p_2^2 + \dots + p_k^2 $$$$$$

Your task is to compute the total harmony level for all unique chords that can be formed with these conditions, then output this value modulo $$$10^9 + 7$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 5 \cdot 10^3$$$) — the target sum of pitches and the exact number of notes in the chord, respectively.

Output

Output a single number representing the total harmony level across all valid chords, modulo $$$10^9 + 7$$$.

Example
Input
5 3
Output
20
Note

There are two valid chords: $$$\{1,1,3\}$$$, and $$$\{1, 2, 2\}$$$. Their values are $$$11$$$ and $$$9$$$ which sum up to $$$20$$$.