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.
K_i 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⁸)
0 ≤ K_i ≤ 1000

Problem Setter: Deepak Singh