Cards

Time limit2sMemory limit512 MB

Summary

Find the probability that L random packs of N equally likely card types meet every demand D_i, output as a fraction mod 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Probability
Solved: No attempts yet

Problem

He started a new strategy card game. To get a card in this game you buy a card pack that holds exactly one card. You cannot see what is inside a pack before opening it. A pack holds one of the $N$ card types in the game, and every type is equally likely.

Collecting the cards is only part of the work. He also has to build decks. Number the cards $1$ through $N$ . To build every deck he wants, he needs at least $D_i$ copies of card $i$ . His goal is therefore to collect $D_i$ or more copies of card $i$ for every $i$ .

Money is the problem. Packs cost money and he does not have much, so he decided to buy only $L$ packs. Write a program that computes the probability that he reaches his goal after opening those $L$ packs.

Input

The first line contains two natural numbers $N$ and $L$ , separated by a space. They are the number of card types and the number of card packs he buys.

The second line contains $N$ integers $D_1, D_2, \dots, D_N$ , separated by spaces, where $D_i$ is how many copies of card $i$ he has to collect.

$1 \le N \le 3000$ , $0 \le D_i \le 10$ , $1 \le L \le 3000$

Output

Print the probability that he reaches his goal. For an exact check, write the answer as a reduced fraction $a/b$ and print $(a \times b^{-1}) \bmod 1000000007$ instead. Here $b^{-1}$ is the multiplicative inverse of $b$ modulo $1000000007$ . The answer exists for every input this problem gives.

Examples4

Example 1
Input
```
1 1
1
```
Expected output
```
1
```
Example 2
Input
```
3 8
3 3 3
```
Expected output
```
0
```
Example 3
Input
```
2 2
1 1
```
Expected output
```
500000004
```
Example 4
Input
```
10 30
0 0 1 1 1 1 1 3 8 9
```
Expected output
```
34678654
```