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

Output

For every case, print the answer modulo 10⁸ + 7.