Permutacions i cicles (2) P64069

Feu un programa que compti quantes permutacions de $\{1, \ldots, n\}$ hi ha amb exactament $k$ cicles, on $1 \le k \le n$.

Per exemple, de les sis permutacions de $\{1, 2, 3\}$, n’hi ha:

• dues amb un cicle, que són: $(2, 3, 1)$ i $(3, 1, 2)$.

• tres amb dos cicles, que són: $(2, 1, 3)$, $(1, 3, 2)$ i $(3, 2, 1)$.

• una amb tres cicles, que és: $(1, 2, 3)$.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $k$, tals que $1 \le k \le n \le 1000$.

Sortida

Per a cada cas, compteu el nombre de permutacions de $\{1, \ldots, n\}$ amb $k$ cicles. Com que el resultat pot ser molt gran, feu els càlculs mòdul $10^8 + 7$.

Observació

Sigui $c$ el nombre de casos. La solució esperada té cost total $O(1000^2 + c)$. Es poden obtenir fins a 80 punts si es passen jocs de proves on $n \le 100$, amb una solució de cost $O(100^3 + c)$.