순열의 좋은 위치

1부터 N까지의 순열 중에서 |P_i - i| = 1을 만족하는 위치가 정확히 K개인 순열의 개수를 10^9+7로 나눈 나머지로 구한다.

보통5조합론동적 계획법수학아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

1부터 NN까지의 수가 각각 한 번씩 들어있는 수열을 크기가 NN인 순열이라 하고, P=P1,P2,,PNP = P_1, P_2, \dots, P_N으로 쓴다.

위치 iiPii=1|P_i - i| = 1을 만족하면 그 위치를 좋은 위치라고 한다.

크기가 NN인 순열 중에서 좋은 위치가 정확히 KK개인 순열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 NNKK가 공백으로 구분되어 주어진다. (1N10001 \le N \le 1000, 0KN0 \le K \le N)

출력

크기가 NN인 순열 중에서 좋은 위치가 정확히 KK개인 순열의 개수를 109+710^9+7로 나눈 나머지를 첫째 줄에 출력한다.