Roses and pots (2) P22292


Statement
 

pdf   zip

thehtml

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

Output

For every case, print the answer modulo 108 + 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++