페리차의 피아노

페리차의 아빠는 즈니다르시치 씨 댁에 다녀오면서, 그동안 피아노를 치고 있으라고 페리차에게 말했다.

피아노에는 건반이 N개 있고, $i$번째 건반에는 값 $a_i$가 적혀 있다. 페리차는 한 번 연주할 때마다 서로 다른 건반을 정확히 K개 동시에 누른다. 이 피아노는 좀 이상해서, 동시에 누른 건반 K개 중 값이 가장 큰 건반 하나만 소리를 낸다.

페리차는 건반 K개를 고르는 모든 방법을 한 번씩 연주한다. 이때 소리가 나는 건반 값의 총합을 1000000007로 나눈 나머지를 구하라.

첫째 줄에 정수 N과 K가 주어진다. ($1 \le N \le 100000$, $1 \le K \le 50$)

둘째 줄에 정수 $a_i$가 N개 주어진다. ($0 \le a_i \le 10^9$)

소리가 나는 건반 값의 총합을 1000000007로 나눈 나머지를 첫째 줄에 출력한다. K가 N보다 크면 건반 K개를 고르는 방법이 없으므로 0을 출력한다.

첫 번째 예제에서 건반 3개를 고르는 방법은 모두 10가지다. 그중 9가지에는 값이 4인 건반이 들어 있어 4가 울리고, 나머지 한 가지는 값이 2, 2, 3인 건반을 누르므로 3이 울린다. 따라서 답은 $9 \times 4 + 3 = 39$다.