시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 28 17 10 62.500%

문제

크기가 N인 수열 A와 정수 K가 주어졌을 때, A의 증가하는 부분 수열 중에서 길이가 K인 것의 개수를 구해보자.

입력

첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A1, A2, ..., AN이 주어진다.

출력

첫째 줄에 A의 증가하는 부분 수열 중에서 길이가 K인 것의 개수를 109+7로 나눈 나머지를 출력한다.

제한

  • 1 ≤ N ≤ 100,000
  • 1 ≤ K ≤ 10
  • 1 ≤ Ai ≤ N
  • Ai는 모두 다른 수

예제 입력 1

5 1
1 2 3 5 4

예제 출력 1

5

예제 입력 2

5 2
1 2 3 5 4

예제 출력 2

9

예제 입력 3

5 3
1 2 3 5 4

예제 출력 3

7

예제 입력 4

5 4
1 2 3 5 4

예제 출력 4

2

예제 입력 5

5 5
1 2 3 5 4

예제 출력 5

0

출처