13184번 - 카드

문제

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

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

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

입력

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

두 번째 줄에는 각 카드마다 모아야 하는 개수를 나타내는 N 개의 정수 D₁, , …, D_N 이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 3,000, 0 ≤ D_i ≤ 10, 1 ≤ L ≤ 3,000)

출력

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

제한

힌트