만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

순열의 좋은 위치

시간 제한2초메모리 제한512 MB

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

보통10점 중 5점

유형
조합론, 동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

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

위치 ii가 ∣Pi−i∣=1|P_i - i| = 1을 만족하면 그 위치를 좋은 위치라고 한다.

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

입력

첫째 줄에 NN과 KK가 공백으로 구분되어 주어진다. (1≤N≤10001 \le N \le 1000, 0≤K≤N0 \le K \le N)

출력

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

예제5

  1. 예제 1

    입력
    1 0
    
    예상 출력
    1
    
  2. 예제 2

    입력
    2 1
    
    예상 출력
    0
    
  3. 예제 3

    입력
    3 2
    
    예상 출력
    4
    
  4. 예제 4

    입력
    4 1
    
    예상 출력
    6
    
  5. 예제 5

    입력
    7 4
    
    예상 출력
    328