Permutations and cycles P99557


Statement
 

pdf   zip

thehtml

Given two natural numbers n and k, let f(n, k) denote the number of permutations with n ‍elements, and such that there are exactly k ‍cycles, all them of length at least 2. Implement a dynamic programming code to compute f(n, k).

Input

Input consists of several cases, each with two natural numbers n and k. You can assume 2 ≤ n ≤ 1000 and 1 ≤ k ≤ ⌊ n/2 ⌋.

Output

For every case, print f(n, k). Because that number can become very large, use long long’s and make the computations modulo 109 + 7.

Hint

You can compute f(n, k) just adding two “recursive calls”.

Public test cases
  • Input

    2 1
    3 1
    4 1
    4 2
    5 1
    5 2
    20 5
    100 10
    1000 1
    1000 2
    1000 500
    

    Output

    1
    2
    6
    3
    24
    20
    796437723
    673801497
    756641425
    592422688
    164644882
    
  • Information
    Author
    Enric Rodríguez
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++