CF285E.Positions in Permutations

Permutation p is an ordered set of integers _p_1,  _p_2,  ...,  p__n, consisting of n distinct positive integers, each of them doesn't exceed n. We'll denote the i-th element of permutation p as p__i. We'll call number n the size or the length of permutation _p_1,  _p_2,  ...,  p__n.

We'll call position i (1 ≤ i ≤ n) in permutation _p_1, _p_2, ..., p__n good, if |p[i] - i| = 1. Count the number of permutations of size n with exactly k good positions. Print the answer modulo 1000000007 (109 + 7).

排列 $p$ 是一个由 $n$ 个互不相同的正整数组成的有序集合 $p_1,\,p_2,\,\dots,\,p_n$，且每个数均不超过 $n$。我们将排列 $p$ 的第 $i$ 个元素记为 $p_i$。我们称 $n$ 为排列 $p_1,\,p_2,\,\dots,\,p_n$ 的大小（或长度）。

在排列 $p_1,\,p_2,\,\dots,\,p_n$ 中，若位置 $i$（其中 $1 \le i \le n$）满足 $|p[i] - i| = 1$，则称该位置为好位置。请计算长度为 $n$ 且恰好有 $k$ 个好位置的排列个数，并将结果对 $1000000007$（即 $10^9 + 7$）取模后输出。

The single line contains two space-separated integers n and k (1 ≤ n ≤ 1000, 0 ≤ k ≤ n).

单行包含两个以空格分隔的整数 $n$ 和 $k$（$1 ≤ n ≤ 1000$，$0 ≤ k ≤ n$）。

Print the number of permutations of length n with exactly k good positions modulo 1000000007 (109 + 7).

输出长度为 $n$ 且恰好有 $k$ 个“好位置”的排列个数对 $1000000007$（即 $10^9 + 7$）取模的结果。

The only permutation of size 1 has 0 good positions.

Permutation (1, 2) has 0 good positions, and permutation (2, 1) has 2 positions.

Permutations of size 3:

1. (1, 2, 3) — 0 positions
2. — 2 positions
3. — 2 positions
4. — 2 positions
5. — 2 positions
6. (3, 2, 1) — 0 positions

大小为 1 的唯一排列有 0 个好位置。

排列 $(1,\,2)$ 有 0 个好位置，而排列 $(2,\,1)$ 有 2 个好位置。

大小为 3 的排列：

1. $(1,\,2,\,3)$ — 0 个好位置
2. — 2 个好位置
3. — 2 个好位置
4. — 2 个好位置
5. — 2 个好位置
6. $(3,\,2,\,1)$ — 0 个好位置