카드 Batch Compilation commands

그는 새로운 전략 카드 게임에 입문했다. 이 게임에서 카드를 구입할 때는 카드가 정확히 하나 들어 있는 카드 팩을 사야한다. 카드 팩 안의 내용물은 뜯어보기 전까지는 알 수 없고 게임에 있는 $N $종류의 카드 중 하나가 들어 있으며 모든 카드는 뽑힐 확률이 동일하다.

카드를 모은다고 끝나는 것이 아니라 덱을 구성해야 한다. 카드에 $1 $번에서 $N $번까지의 번호를 붙이면, 그가 원하는 덱들을 구성하기 위해서는 $i $번 카드가 적어도 $D_{i} $장은 필요하다. 그러므로 그의 목표는 각 카드 $i $에 대해 $D_{i} $개 이상의 카드를 모으는 것이다.

하지만 현실은 그다지 녹록치 않다. 카드 팩은 돈을 주고 사야하고 그가 가진 돈은 적기 때문이다. 결국 그는 카드 팩을 $L $개만 구매하기로 했다. 그가 그의 목표를 달성할 확률을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 카드의 종류, 사려고 하는 카드 팩의 수를 나타내는 두 자연수 $N, L $이 공백으로 구분되어 주어진다.

두 번째 줄에는 각 카드마다 모아야 하는 개수를 나타내는 $N $개의 정수 $D_{1}, , \ldots, D_{N} $이 공백으로 구분되어 주어진다.

부분문제

부분문제	점수	N	각 Di	L
1	13	1 ≤ N ≤ 3,000	0 ≤ Di ≤ 1	1 ≤ L ≤ 3,000
2	87	1 ≤ N ≤ 3,000	0 ≤ Di ≤ 10	1 ≤ L ≤ 3,000

출력

그가 목표를 달성할 확률을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 가 된다면, 을 대신 출력하도록 한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

입출력 예제

예제 1

입력

1 1
1

출력

1

예제 2

입력

3 8
3 3 3

출력

0

예제 3

입력

2 2
1 1

출력

500000004

예제 4

입력

10 30
0 0 1 1 1 1 1 3 8 9

출력

34678654

세 번째 예제의 답은 $1/2$를 의미한다.