Positions in Permutations

称一个 $1\sim n$ 的排列的完美数为有多少个 $i$ 满足 $|P_i-i|=1$ 。 求有多少个长度为 $n$ 的完美数恰好为 $m$ 的排列。答案对 $10^9+7$ 取模。 $1 \le n \le 1000,0 \le m \le n$。

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 $ ( $ 10^{9}+7 $ ).

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

Print the number of permutations of length $ n $ with exactly $ k $ good positions modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

1 0

1

2 1

0

3 2

4

4 1

6

7 4

328

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