(i, j) with i < j but a[i] > a[j].
You are given n and a list of rules rules, where rules[t] = [end, cnt] says that the prefix of the permutation from index 0 to end inclusive contains exactly cnt inversions.
How many permutations of 0, 1, ..., n - 1 satisfy all the rules at once? Return the count modulo 10⁹ + 7.n=3, rules=[[2, 1]] → 2
Exactly one inversion in the whole permutation: [1, 0, 2] and [0, 2, 1].
n=4, rules=[[3, 3], [1, 0]] → 3
The first two elements must be in increasing order with three inversions overall. Exactly three permutations fit: [0, 3, 2, 1], [1, 2, 3, 0] and [1, 3, 0, 2].
n=3, rules=[[0, 1], [2, 1]] → 0
A one-element prefix never has an inversion, so no permutation fits.
end values are distinct, and one of them is n - 1n=3, rules=[[2, 1]]
2
Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.