To My Girlfriend

Time Limit: 2000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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
$$
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}\sum_{m=1}^{s}f(i,j,k,l,m)\quad (i,j,k,l\quad are\quad different)
$$

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).

Sample Input

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

Sample Output

8 8

Hint

wange2014

Source

2016 Multi-University Training Contest 6

提交代码