Migrated from Lutece 1451 To My Girlfriend

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Dear Guo

I never forget the moment I met with you.You carefully asked me: "I have a very difficult problem. Can you teach me?".I replied with a smile, "of course"."I have n items, their weight was a[i]",you said,"Let's define f(i,j,k,l,m) to be the number of the subset of the weight of n items was m in total and has No.i and No.j items without No.k and No.l items.""And then," I asked.You said:"I want to know

Sincerely yours, Liao

Input

The first line of input contains an integer T$(T\le 15)$ indicating the number of test cases.

Each case contains 2 integers $n$, $s$ $(4\le n\le 1000,1\le s\le 1000)$. The next line contains n numbers: $a_1,a_2,\dots,a_n$ $(1\le a_i\le 1000)$.

Output

Each case print the only number — the number of her would modulo $10^9+7$ (both Liao and Guo like the number).

Samples

2
4 4
1 2 3 4
4 4
1 2 3 4

8
8

Resources

2016 Multi-University Training Contest 6