Given positive integers $N$ and $M$, there are $N$ pairs of distinct parentheses. Arranging them in any order results in a sequence of parentheses, with a total of $(2N)!$ possible permutations.
A sequence of parentheses is called valid if and only if the difference between the indices of each pair of parentheses is not a multiple of $M$.
Find the number of valid parenthesis sequences modulo $10^9+7$.
Input
A single line containing two positive integers $N$ and $M$.
Output
A single line containing a non-negative integer representing the answer.
Examples
Input 1
1 1Output 1
0Input 2
3 2Output 2
288Input 3
300 300Output 3
929890502Input 4
100 23Output 4
171243255Input 5
2000 1000Output 5
348739341Constraints
For all test cases, $M\le N\le 2000$.
| Subtask ID | $N\le$ | Score |
|---|---|---|
| $1$ | $5$ | $1$ |
| $2$ | $100$ | $1$ |
| $3$ | $300$ | $1$ |
| $4$ | $900$ | $2$ |
| $5$ | $2000$ | $2$ |