알파카 목장에 \(N\)마리의 알파카가 한 줄로 서 있다. 왼쪽부터 \(i\)번째 알파카의 키는 \(Arr_i\)이다.

목장 주인은 사진을 찍으려고 하는데, 키가 들쭉날쭉해서 영 마음에 들지 않는다. 그래서 줄에서 알파카 몇 마리만 골라 따로 세워, 왼쪽에서 오른쪽으로 갈수록 키가 점점 작아지는 예쁜 내리막 줄을 만들고 싶어 한다.

단, 알파카들은 자존심이 세서 원래 서 있던 순서(왼쪽→오른쪽)는 절대 바꾸지 않는다. 즉 골라낸 알파카들은 원래 줄에서의 순서를 그대로 유지해야 한다.

주인은 정확히 \(K\)마리를 골라 다음을 만족시키고 싶다.

• 고른 알파카들의 원래 위치가 \(i_1 < i_2 < \dots < i_K\) 이고,
• 그 키가 \(Arr_{i_1} > Arr_{i_2} > \dots > Arr_{i_K}\) 으로 순서대로 점점 작아진다.

이런 식으로 \(K\)마리를 골라 내리막 줄을 만드는 방법이 총 몇 가지인지 궁금하다. 같은 키여도 자리가 다르면 다른 알파카이므로, 키가 같은 두 마리는 한 줄에 함께 설 수 없다(키가 엄격히 작아져야 한다).

경우의 수가 어마어마하게 클 수 있으니, 답을 \(10^9 + 7\)로 나눈 나머지를 출력하여라.

• 주어지는 모든 수는 정수이다.
• \(2 \le K \le 50\)
• \(K \le N \le 10^5\)
• \(-10^9 \le Arr_i \le 10^9\)

첫째 줄에 두 정수 \(N\), \(K\)가 공백으로 구분되어 주어진다.

둘째 줄에 알파카들의 키 \(Arr_1, Arr_2, \dots, Arr_N\)이 공백으로 구분되어 주어진다.

조건을 만족하도록 \(K\)마리를 고르는 방법의 수를 \(10^9+7\)로 나눈 나머지를 첫째 줄에 출력한다.

rip 작성

출처 알파카컵 4회