Count permutations with exactly n inversions

Q: Count permutations with exactly n inversions

This is a Coding & Algorithms interview question from Turing for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given two integers m and n.

Consider all permutations of the array [1, 2, ..., m] (each number from 1 to m appears exactly once). A permutation perm (0-indexed) has an inversion pair (x, y) if:

0 <= x < y < m , and
perm[x] > perm[y]

A permutation is called special if it contains exactly n inversions.

Return the number of special permutations modulo 10^9 + 7.

Examples

Input: m = 3, n = 0
Output: 1
Explanation: Only [1, 2, 3] has 0 inversions.
Input: m = 3, n = 1
Output: 2
Explanation: [1, 3, 2] and [2, 1, 3] each have exactly 1 inversion.

Constraints

1 <= m <= 1000
0 <= n <= 1000

Count permutations with exactly n inversions

Examples

Constraints

Comments (0)