Eating machine (2) P80631

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⁸ + 7.