시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 41 17 14 60.870%

문제

어떤 길이 N의 순열이 있다고 한다. 이 순열은 0~N-1 까지의 수로만 이루어져 있다. a = {a[0], a[1], ... , a[n-1])

진영 순열이란 b[a[i]] = i를 만족하는 순열을 말한다.

예를 들어, (2, 0, 3, 1, 4)의 진영 순열은 (1, 3, 0, 2, 4)이다.

진영 순열을 약간 업그레이드한 순열이 존재하는데 그 이름은 K-진영 순열이다.

A가 K-진영 순열이라는 것은 A의 진영 순열인 B가 정확히 b[i] > b[i+1]를 만족하는 i를 정확히 K개 가지는 것을 의미한다.

예를 들어, (2, 0, 3, 1, 4)은 1-진영 순열이다. 그 이유는 (2, 0, 3, 1, 4)의 진영 순열인 (1, 3, 0, 2, 4)에서 b[i] > b[i+1]를 만족하는 i가 단 한 개 존재하기 때문이다.

N과 K와 A[0]이 주어졌을 때, 길이가 N이면서 K-진영 순열인 순열의 개수를 구하는 프로그램을 작성하시오.

예를 들어, N=4, K=1, A[0] = 0일 때, (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2)만이 N=4이면서 1-진영 순열이기 때문에 답은 4이다.

입력

첫째 줄에 N, 둘째 줄에 K, 셋째 줄에 A[0],이 주어진다. (1<=N<=20, 0<=K<=N-1, 0<=A[0]<=N-1)

출력

첫째 줄에 길이가 N이고 첫 번째 수가 A[0]인 K-진영 순열인 것의 개수를 출력한다.

예제 입력

7
3
2

예제 출력

330

힌트

출처