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++
- Event
- Desè Concurs de Programació de la UPC - Final
- Date
- 2012-09-15