시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 0 0 0 0.000%

문제

You are given an integer set $A=\{a_1,a_2,\ldots,a_n\}$. Please calculate the number of solutions for equation $x_1+x_2+\ldots+x_k=m$, where $x_i$ are positive integers, $x_1 \le x_2 \le \ldots \le x_k$ and $x_i \not \in A$.

As the answer may be very large, you are only asked to calculate it modulo $(10^9 + 7)$.

입력

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \le 500$, $n \le m \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le m$, $a_i \ne a_j$ for all $i \ne j$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

출력

For each test cases, output an integer denoting the answer.

예제 입력 1

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

예제 출력 1

2
3
4
1
0

힌트

There are $5$ solutions for $m=4$ if the constraints set $A$ is empty. They are: $$ \begin{aligned} 4 & = & 1+1+1+1 \\ {} & = & 1+1+2 \\ {} & = & 1+3 \\ {} & = & 2+2 \\ {} & = & 4 \end{aligned} $$