Hi Codeforces community,

Recently I have come across a problem which turned out to be tough for me. I hope that I can get some help from you.

## Problem Statement

A permutation *A* of first *N* integers from 1 to *N* is good if it has exactly *K* good positions. A position *i* is good only if *abs*(*A*[*i*] - *i*) = 1. The task is to count how many permutation of first *N* integers like that, modulo 10^{9} + 7.

### Input

*N* and *K*, 1 ≤ *N* ≤ 1000, 0 ≤ *K* ≤ *N*

### Output

Number of permutation of first *N* integers from 1 to *N* that has exactly *K* good positions, modulo 10^{9} + 7

#### Example

For *N* = 3, *K* = 2, there are 4 permutations that has 2 good positions. They are (1, 3, 2) , (2, 1, 3) , (2, 3, 1) , (3, 1, 2).

You may want to submit your solution here (written in Vietnamese, required SPOJ account): http://www.spoj.com/PTIT/problems/P172PROI/

I think it is a DP problem although I could not come up with a solution or any idea. Any help will be appreciated.

Thanks in advance.