#2773 재재새와 울트라 박스

1 s   128 MB  

Description

재재새는 영화를 좋아한다.

 

특히, 재재새는 울트라 박스 영화관에서 영화를 보는 것을 좋아 한다.

 

어느날 재재새는 영화관에서 좌석을 확인하다가, 재미난 일을 경험하였다.

 

덩치가 큰 몇명을 제외하고, 마른 친구들 끼리 좌석을 바꿔 앉는 것이었다.

 

그런데, 그냥 자리를 바꿔 앉는게 아니라, 이웃한 친구 끼리만 좌석을 바꿔 앉는 것이다.

 

그런데 또 무조건 바꿔 앉는게 아니라, 바꿔 앉고 싶은 사람 끼리만 바꿔 앉는 것이다.

 

예를들면, 4명의 사람이 있는데, 각각을 1번 부터 4번이라고 하자.

 

3번 친구는 덩치가 큰 사람이다.

1번, 2번, 4번 친구는 마른 사람이다.

 

이들이 앉는 경우의 수는

 

1, 2, 3, 4

2, 1, 3, 4

 

이렇게 2가지 경우의 수다.

 

하나의 예를 더 들어보자.

 

1~4번이 있는데, 4번이 덩치가 큰 사람일 때,

 

경우의 수는

 

1, 2, 3, 4

2, 1, 3, 4

1, 3, 2, 4

 

이렇게 3가지 이다.

 

 

 

이제부터, 재재새를 위해

 

N명의 사람 중, K명의 덩치 큰 사람을 각 각 $k_1, k_2, k_3, \dots k_k$라 했을 때,

 

이들을 배열 하는 경우의 수를 출력 하라.

Input

$N (1 \leq N \leq 100)$

$K (0 \leq K \leq N)$

$1 \leq k_i \leq N, i \leq N$

Output

정답이 너무 클 수 있으므로,

 

정답이 3001보다 클 경우, 3001로 나눈 나머지를 출력 하라.

Sample Input

Sample Output

10 3
1 2 9
13

Source

wowoto9772