Jan is an eating machine. At this moment, he is in front of a table with c different kinds of cakes. He wants to eat cake exactly n times, but with two restrictions:

- Every kind of cake must be tasted at least once.
- He wants to repeat at least with half of the kinds of cakes.

Given n and c, can you compute the number of ways of eating cakes? The eating order matters. For instance, if there are three kinds of cakes, say A B and C, and Jan wants to eat cake six times, these are some of the 450 possibilities: AAABBC, ABABAC, AACCBB. Note that AAAABC is not an allowed combination.

Input

Input consists of several cases, each with n and c. Assume 2 ≤ n ≤ 80, and that for each given combination there is at least one way of eating cake.

Output

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

Public test cases

**Input**

2 1 3 2 4 2 6 3 80 53

**Output**

1 6 14 450 61087945

Information

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