Given positive integers $n, m$ ($n < m$), an integer sequence of length $n$ is called a "good sequence" if it satisfies the following condition:
- $0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq m$.
For a good sequence $a$, let $f(a)$ be the sequence obtained by sorting $(a_1-1, a_2-2, \dots, a_n-n)$ in ascending order.
For each $k = 1, 2, \dots, n$, solve the following problem:
- Calculate the sum of the $k$-th largest elements of $f(a)$ over all good sequences $a$, modulo $10^9+7$.
Input
A single line containing two positive integers $n, m$.
Output
Output $n$ lines, each containing a non-negative integer, where the $i$-th line is the answer for $k=i$.
Examples
Input 1
2 3
Output 1
1000000003 4
Input 2
3 4
Output 2
999999983 0 24
Input 3
4 6
Output 3
999999887 35 175 330
Input 4
10 1000000
Output 4
137169236 227221797 992684263 740277343 939871578 109754271 309348506 56941586 822404052 912456613
Constraints
For all test cases, it is guaranteed that $1 \leq n < m < 10^6$.
| Subtask | Special Properties | Score |
|---|---|---|
| $1$ | $n, m \leq 10$ | $10$ |
| $2$ | $n, m \leq 100$ | $15$ |
| $3$ | $n, m \leq 500$ | $15$ |
| $4$ | $n, m \leq 5000$ | $15$ |
| $5$ | $m-n \leq 10$ | $15$ |
| $6$ | $n \leq 10$ | $15$ |
| $7$ | $15$ |