You are given an array arr of size n and an integer k. Score of an array is defined as number of its non-empty subarrays with sum = k. Your task is to find sum of scores of all the subsequences of arr. Since the answer can be very large print its modulo 1e9+7.

Input format :

First line contains T , the number of testcases. Each testcase has two lines. First line contains two integers n and k. Second line contains n integers describing arr.

Output Format :

For each testcase, print a single integer denoting sum of scores of all the subsequences of arr modulo 1e9+7

Constraints :

1<=T<=1000 1<=n<=1000 1<=k<=1000 1<=arr[i]<=1e5 Sum of n over all the testcases will not exceed 1000 Sum of k over all the testcases will not exceed 1000.

First Test Case

2

10 1

5 1 4 5 4 5 3 3 2 2

10 2

2 2 5 1 2 3 2 1 2 4

Output:

512

2592

Dry run:

For 1st tc, for subarray [1] there are 9-left out elements, possibility of taking-not-taking = 2^9 = 512 no other subarray possible, hence ans = 512

For 2nd tc, for subarray [2], there are 5 such subarrays, possibility of other 9 elements = 2 ^ 9 = 512 (for each) there are 5 such, hence ans for subarray [2] = 5 x 512 = 2560 now there is one more possible subarray [1,1], to make this as a subarray we need to exclude all the elements in between, hence new array = [2,2,5,1,1,2,4], now keeping [1,1] aside, we are left with 5 other element, possibility = 2 ^ 5 = 32 no other subarray possible

hence ans = 2560 + 32 = 2592