A Math Contest P8 - Permutation Counting

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 512M

Author:
Problem types

Calculate the number of permutations of the first N positive integers which can be sorted by performing exactly K swaps of adjacent elements.

Constraints

2 \le N \le 3\,000

0 \le K \le 3\,000

Input Specification

The only line contains two space-separated integers, N and K.

Output Specification

Output the number of permutations of the first N positive integers which can be sorted by performing exactly K adjacent swaps. Since this value may be large, output it modulo 10^9+7.

Sample Input

3 3

Sample Output

3

Explanation for Sample

The permutations of [1, 2, 3] which can be sorted by performing exactly 3 adjacent swaps are [2, 1, 3], [1, 3, 2] and [3, 2, 1].


Comments

There are no comments at the moment.