17409번 - 증가 수열의 개수

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

첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A₁, A₂, ..., A_N이 주어진다.

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

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