Marisa has $n$ bookshelves, the $i^{th}$ shelf contains $A_i$ books.
She wants to take out $k$ books to read. She will take at most $1$ book from each bookshelf. How many ways can she choose $k$ books?
### Input
- The first line contains 2 integers $n, k$.
- The second line contains $n$ integers $A_i$.
### Output
- Print one integer, the number of ways modulo $10^9+7$.
### Constraints
- $1 \le k \le n \le 1000$.
- $1 \le A_i \le 10^9$.
### Example
Input:
```
3 2
1 2 1
```
Output:
```
5
```
Note: There are $5$ ways:
- $(1_1, 2_1)$
- $(1_1, 2_2)$
- $(1_1, 3_1)$
- $(2_1, 3_1)$
- $(2_2, 3_1)$
where $x_y$ is the $y^{th}$ book from shelf $x$.
