Problem Description
Coco the Monkey is performing at a circus and is currently handing out colourful balloons to the audience.
Coco the Monkey has balloons of N colours numbered from 1 to N. Coco the Monkey has Ai balloons of the ith colour. Each person in the audience gets exactly K balloons.
Damian and Fan Pu have come to see Coco the Monkey perform at the circus. As they watch Coco the Monkey distribute balloons, Damian wonders, how many different possible combinations of colours of balloons Coco the Monkey can give someone in the audience? Two combinations are considered distinct if the number of balloons present in one combination and in another combination is different for a certain colour.
Damian asks Fan Pu his question, but Fan Pu wants to watch the performance. As such, can you help Damian calculate the answer, modulo 109 + 7?
Input
The first line of input will contain two integers, N and K.
The following line of input will contain N space separated integers, Ai.
Output
Output a single integer, the number of distinct combinations, modulo 109 + 7.
Limits
Subtask 1 (14%): 1 ≤ N ≤ 3. 1 ≤ K ≤ 1500. 1 ≤ Ai ≤ 1000.
Subtask 2 (29%): 1 ≤ N ≤ 20. 1 ≤ K ≤ 104. 1 ≤ Ai ≤ 1000.
Subtask 3 (57%): 1 ≤ N ≤ 20. 1 ≤ K ≤ 1014. 1 ≤ Ai ≤ 1012.
Subtask 4 (0%): Sample Testcases
Sample Testcase 1
Input
3 5
1 3 2
Output
3