3674 - Positions in Permutations

3674.Positions in Permutations

Time Limit: 1s Memory Limit: 256MB

Permutation p is an ordered set of integers p1,p2,...,pn, consisting of n distinct positive integers, each of them doesn't exceed n. We'll denote the i-th element of permutation p as pi. We'll call number n the size or the length of permutation p1,p2,...,pn.We'll call position i (1 \le i \le n) in permutation p1,p2,...,pn 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).

Input Format(From the terminal/stdin)

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

Output Format(To the terminal/stdout)

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

Sample Input 1

Copy

1 0
 · \n

Sample Output 1

Copy

1
 \n

Sample Input 2

Copy

2 1
 · \n

Sample Output 2

Copy

0
 \n

Sample Input 3

Copy

3 2
 · \n

Sample Output 3

Copy

4
 \n

Sample Input 4

Copy

4 1
 · \n

Sample Output 4

Copy

6
 \n

Sample Input 5

Copy

7 4
 · \n

Sample Output 5

Copy

328
   \n

Hints

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,2,3) - 0 positions $3674_1.png$ - 2 positions $3674_2.png$ - 2 positions $3674_3.png$ - 2 positions $3674_4.png$ - 2 positions (3,2,1) - 0 positions

Submit

请先登录

Submit

题解(0)