25345번 - 루나의 게임 세팅

루나와 리나는 타워 건설 게임을 하려고 한다. 타워 건설 게임은 $K$개의 타워를 사용하는 게임이고 루나는 이 게임을 세팅하려고 한다. 

게임 세팅은 서로 다른 높이의 $N$개의 타워 중 $K$개를 선택해 원하는 순서로 일렬로 배치하는 것이다. 이때 앞과 뒤에서 바라볼 때 모든 타워가 최소 한 번은 보여야 한다. 즉, 어떤 타워에 대해서 그보다 높은 타워가 그 타워의 앞쪽과 뒤쪽에 모두 존재하면 안된다는 것이다. 

게임 세팅을 하던 루나는 문득 게임을 세팅하는 방법이 얼마나 많을 지가 궁금해졌다. 루나를 도와서 게임 세팅을 하는 경우의 수를 구해보자. 

첫째 줄에는 두 양의 정수 $N$과 $K$가 주어진다.

둘째 줄에는 각각의 타워의 높이 $A_{1}, A_{2}, \cdots, A_{N}$이 공백으로 구분되어 주어진다.

모든 입력은 정수이다.

게임 세팅을 할 수 있는 경우의 수를 $10^{9}+7$로 나눈 나머지를 출력한다. 

• $1 \leq K \leq N \leq 2000$
• $1 \leq A_{i} \leq 10^{9}$
• 모든 $A_i$는 서로 다른 정수이다.