Cman doesn't love math anymore. He loves Alisha. Alisha is cute. :)
Cman goes on a date with her. They go to a candy shop. Alisha loves candies. The shop has n number of jars, each jar having a different type of candy.
Alisha wants to taste all type of candies so she asks Cman to buy candies for her. She also asks Cman to buy at least X[i] candies of type i. Cost of each candy is $1. Cman has forgotten to bring his wallet so the poor guy has no money.
Cman has to anyhow buy these candies for Alisha. So, he asks the shopkeeper for help and looking at the condition of Cman, the shopkeeper agrees to help Cman but on a condition. Shopkeeper puts the condition that he will give Cman candies of $R for free if Cman can tell him the total number of ways to select the candies such that it fulfills Alisha's condition of getting at least X[i] candies of type i and also the sum of candies result in total cost of exactly $R.
As things are awkward between Cman and math currently, he asks you for help. So, your task is to help Cman to find the resulting number of ways modulo 10^9 +7 so that he can get candies for free and can make Alisha happy.
P.S. : Alisha will give a kiss to Cman if he buys the required number of candies for her. So, your task is to help Cman to get a kiss. :’)


Input :
First line of input will contain an integer T representing number of test cases. First line of each test case will contain two space separated integer N and R representing number of jars and amount in dollar which shopkeeper is going to give cman if he completes the required task. Second line of test case contain N space separated integer X[i] representing the minimum number of candies required of type i.

Output :
Print T lines each contain a single integer representing the number of ways modulo 10^9 + 7.

Constraints :
1<=T<=10
1<=N<=100000
1<=X[i]<=3
X[1]+X[2]+...+X[N] < R < 400000