Eating machine (2) P80631


Statement
 

pdf   zip

html

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 108 + 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++