시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB2881269841.525%

문제

크기가 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

출처