Permutacions i cicles P99557

Donats dos naturals $n$ i $k$, sigui $f(n, k)$ el nombre de permutacions amb $n$ elements, i les quals contenen exactament $k$ cicles, tots ells de longitud 2 o més. Implementeu una programació dinàmica que calculi $f(n, k)$.

Entrada

L’entrada consisteix en diversos casos, cadascun amb dos naturals $n$ i $k$. Podeu suposar $2 \le n \le 1000$ i $1 \le k \le \lfloor n/2 \rfloor$.

Sortida

Per a cada cas, escriviu $f(n, k)$. Com que aquest nombre pot ser molt gran, useu @long long@’s i feu els càlculs mòdul $10^9 + 7$.

Pista

Es pot calcular $f(n, k)$ com la suma de només dues “crides recursives”.