Permutations and cycles (2) P64069


Statement
 

pdf   zip

thehtml

Write a program to count the number of permutations of {1, …, n} with exactly k cycles, where 1 ≤ kn.

For instance, of the six permutations of {1, 2, 3}, we have:

  • two with one cycle, which are: (2, 3, 1) and (3, 1, 2).
  • three with two cycles, which are: (2, 1, 3), (1, 3, 2) and (3, 2, 1).
  • one with three cycles, which is: (1, 2, 3).

Input

Input consists of several cases, each with n and k, such that 1 ≤ kn ≤ 1000.

Output

For every case, count the number of permutations of {1, …, n} with k cycles. As the result can be very large, make the computations modulo 108 + 7.

Observation

Let c be the number of cases. The expected solution has total cost O(10002 + c). You can get up to 80 points with test cases where n ≤ 100, with a solution with cost O(1003 + c).

Public test cases
  • Input

    3 1
    3 2
    3 3
    4 1
    4 2
    4 3
    4 4
    10 2
    20 10
    100 50
    

    Output

    2
    3
    1
    6
    11
    6
    1
    1026576
    28767655
    68128793
    
  • Information
    Author
    Enric Rodríguez
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++