1부터 N까지의 순열 중에서 |P_i - i| = 1을 만족하는 위치가 정확히 K개인 순열의 개수를 10^9+7로 나눈 나머지로 구한다.
1부터 NNN까지의 수가 각각 한 번씩 들어있는 수열을 크기가 NNN인 순열이라 하고, P=P1,P2,…,PNP = P_1, P_2, \dots, P_NP=P1,P2,…,PN으로 쓴다.
위치 iii가 ∣Pi−i∣=1|P_i - i| = 1∣Pi−i∣=1을 만족하면 그 위치를 좋은 위치라고 한다.
크기가 NNN인 순열 중에서 좋은 위치가 정확히 KKK개인 순열의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 NNN과 KKK가 공백으로 구분되어 주어진다. (1≤N≤10001 \le N \le 10001≤N≤1000, 0≤K≤N0 \le K \le N0≤K≤N)
크기가 NNN인 순열 중에서 좋은 위치가 정확히 KKK개인 순열의 개수를 109+710^9+7109+7로 나눈 나머지를 첫째 줄에 출력한다.