Permutations and cycles P99557

Given two natural numbers $n$ and $k$, let $f(n, k)$ denote the number of permutations with $n$ elements, and such that there are exactly $k$ cycles, all them of length at least 2. Implement a dynamic programming code to compute $f(n, k)$.

Input

Input consists of several cases, each with two natural numbers $n$ and $k$. You can assume $2 \le n \le 1000$ and $1 \le k \le \lfloor n/2 \rfloor$.

Output

For every case, print $f(n, k)$. Because that number can become very large, use @long long@’s and make the computations modulo $10^9 + 7$.

Hint

You can compute $f(n, k)$ just adding two “recursive calls”.