Regular Polygon Triangulation Problem: Given $n$ and $k$, find the number of ways to perform a $k$-angulation of a convex $nk-2(n-1)$-gon, modulo $10^9+7$.

Input

Each test case contains multiple queries.

The first line of the input contains two integers $n, k$.

Output

Output a single integer representing the sum of the answers for all queries.

Examples

Input 1

2 3
3 3
3 4

Output 1

19

Subtasks

For $50\%$ of the data, $n \leq 5\,000$.

For $100\%$ of the data, $k \leq 200, n \leq 1\,100\,000$.

Notes

1. The number of test cases was not provided during the contest, "participants should estimate it themselves".
2. The lower bound of $k$ was not provided during the contest, and the author claimed during the Q&A that they do not guarantee $k \nleq 2$ (although there are none in the data).
3. The memory limit was not provided during the contest, "participants should estimate it themselves", and is set to 1 GB on QOJ.