Mr Nikhil has k Children. They are suffering from a disease called Gasomia . According to his family Doctor , Child 1 requires atleast x1 tablets , Child 2 requires atleast x2 ......... Child k requires atleast xk tablets. As Nikhil got job in Golden Ship,he bought m tablets and wants to distribute all the tablets among his children.Can you tell him the number of ways of distributing tablets among children in such a way,that all the children get satisfied. As the numbers of ways can be very large, print ans mod 1000000007

Input

First line of the input contains T , denoting number of test cases

For each test case it contains two integers k and m denoting— number of children and the number of tablets he have respectively.

Then follow k numbers , denoting minimum tablets needed by child i, 1≤ i ≤ k

Output

Print the number of ways % 1000000007.

Subtasks

Subtask #1: (15points) 1 ≤ T ≤ 10, 2 ≤ k  ≤ 10, 1 ≤ m ≤1000,1 ≤ x1,x2...xk ≤20.

Subtask #2: (25points) 1 ≤ T ≤ 10, 2 ≤ k ≤ 50, 1 ≤ m≤ 10000,1 ≤ x1,x2...xk ≤100.

Subtask #2: (60points) 1 ≤ T ≤ 100, 2 ≤ k ≤ 1000, 1 ≤ m≤ 100000,1 ≤ x1,x2...xk ≤100.