H. Banis Hotel
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The city of Banis has a hotel consisting of $$$n$$$ floors.

The $$$i$$$-th floor (from the bottom) can withstand a weight of $$$w_i$$$ (i.e., there should be no more than $$$w_i$$$ clients on the $$$i$$$-th floor $$$\textbf{or above}$$$, otherwise, the hotel would collapse).

The hotel manager expects $$$m$$$ clients to come to the hotel this month, and each client has a certain rank.

If the rank of client $$$i$$$ is $$$r_i$$$ ($$$1 \le r_i \le n$$$), then the manager would want them to be on the $$$r_i$$$-th floor or lower.

However, he does not know the ranks of the clients. Therefore, $$$r_i$$$ can be from $$$1$$$ to $$$n$$$ with equal probability.

If a client is placed on the $$$i$$$-th floor, they would give the hotel a rating of $$$i$$$.

As a part of the hotel's staff, you need to place the clients optimally to get the maximum possible sum of ratings (but while still satisfying the conditions mentioned above).

Let $$$X$$$ be the sum of the ratings that each client gives.

What is the expected value of $$$X$$$ if you place the $$$m$$$ clients optimally? You should print the answer modulo $$$10 ^ 9 + 7$$$.

Input

The first line of the input consists of two space-separated integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2000$$$) — the number of floors and the number of clients, respectively.

The second line of the input consists of $$$n$$$ space-separated integers $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 2000$$$) — the $$$i$$$-th of which denotes the weight that the $$$i$$$-th floor can withstand.

It's guaranteed that $$$w_1 \ge m$$$ and $$$w_1 \ge w_2 \ge \dots \ge w_n$$$.

Output

Output one line containing a single integer — the expected value of the sum of ratings that each client would give to the hotel if they were placed optimally, taken modulo $$$10 ^ 9 + 7$$$.

It is guaranteed that the answer can always be represented as an irreducible fraction $$$\frac{a}{b}$$$, where $$$b \mod (10^9 + 7) \ne 0$$$; you have to print $$$a \cdot b^{-1} \mod (10^9 + 7)$$$.

Examples
Input
5 2
5 5 4 4 4
Output
6
Input
5 1
1 1 1 1 1
Output
3
Input
3 7
7 3 1
Output
888888906