| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 27 | 15 | 12 | 85.714% |
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.
5 1 4 1 1 4 2 1 4 3 3 4 1 2 3 4 4 1 2 3 4
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} $$