Nombre de permutation avec K inversions

Question

On nous donne deux nombres N et K.

N <= 10 ^ 9.

K <= min {1000, (n * (n-1)) / 2}

Nous devons trouver un nombre de permutations de (1 à n) de sorte que les inversions sont exactement K.

Si n était <= 10 ^ 3. Ce serait une simple question de programmation dynamique.

https://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/

Pouvons-nous l'optimiser?