Numero di permutazione con inversioni K

Question

Ci vengono dati due numeri N e K.

N <= 10^9.

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

Dobbiamo trovare un numero di permutazioni da (1 a n) in modo tale che le inversioni siano esattamente K.

Se n era <= 10^3. Sarebbe una semplice domanda di programmazione dinamica.

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

Possiamo ottimizzarlo?