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 ≤ n ≤ 10^{7}.
For c = 3, we have 1 ≤ n ≤ 200.

Output

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

Public test cases

**Input**

2 2 3 1 3 2 3 200

**Output**

2 0 36 73999084

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++