Różnokolorowe kulki

Limit czasu: 0.5s | Limit pamięci: 64MB

Jaś ma piękną kolekcję kulek. Jego kulki są w $n$ różnych kolorach. Zastanawia się on na ile sposobów może wybrać $k$ kulek ze swojej kolekcji, tak żeby żadne dwie wybrane kulki nie były tego samego koloru.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ i $k$. Drugi wiersz zawiera $n$ liczb całkowitych $a_i$, oznaczających że $a_i$ kulek jest koloru $i$.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą – resztę z dzielenia odpowiedzi na pytanie Jasia przez $10^9+7$.

Ograniczenia

• $1 \le k \le n \le 1\,000$
• $a_i \ge 1$
• $\sum a_i \le 10^6$

Przykłady

Wejście 1

3 2
1 2 3

Wyjście 1

11

Wejście 2

4 3
1 1 1 10

Wyjście 2

31