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 \le n \le 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$.