sleeping-pills

Professor MAZ has habit of throwing sleeping pills in the class while taking lectures.
There are N students in class. Every students need different dose to sleep in his class during the lecture.
Ki denotes the minimum number of dose of sleeping pills required for i^th student to sleep in his class.
You will be given an array of N values, each value denoting dose capacity of i^th student.
Prof MAZ has total number of M sleeping pills.
You have to find total number of ways he can distribute those pills among students so that whole class will sleep :P
As the answer can be very large take the modulo with 1000000007.  

Input:
The first line contains single integer T number of test cases. 
The next line contains two integer N and M
Next line contains N space separated integer which is the minimum dose of i^th student.   

Output:
Print the answer modulo 1000000007.  

Constraints: 
1 ≤ T ≤ 100 
1 ≤ N ≤ 100000 
1 ≤ M ≤ 100000000 (10^8)
0 ≤ Ki ≤ 1000

Problem Setter: Deepak Singh

SAMPLE INPUT
3 
4 10 
2 1 2 1 
5  20 
5 9 6 3 2 
10 1000 
200 10 20 13 32 50 21 19 12 109

SAMPLE OUTPUT
35 
0 
575817000

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: