Roses and pots (2) P22292

You have roses of $c$ different colors. In particular, you have $n$ roses of each color. Please compute the number of ways to plant all the roses in a line of $cn$ pots, one rose per pot, in such a way that there is exactly one pair of adjacent roses of the same color. The roses of the same color are indistinguishable.

Input

Input consists of several cases, each with $c$ and $n$. Assume that $c$ is either 2 or 3. For $c = 2$, we have $1 \le n \le 10^7$. For $c = 3$, we have $1 \le n \le 200$.

Output

For every case, print the answer modulo $10^8 + 7$.