L. The Vault of Stars
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The mysteries of the universe have long been engraved in the alignment of the stars...

After enduring countless hardships, explorer Little A has finally stepped into the ultimate region of the Astra ruins—the Vault of Stars.

Suspended in the center of the vault are $$$S$$$ pure starlight crystals, surrounded by $$$N$$$ ancient array pillars of various shapes. To completely stabilize the energy field of the ruins, Little A must distribute all $$$S$$$ crystals into these $$$N$$$ pillars.

Every pillar has a limit to the energy it can withstand. Specifically, the $$$i$$$-th pillar can hold at most $$$L_i$$$ crystals. Of course, Little A can also choose not to place any crystals in certain pillars (i.e., the allocated amount is 0).

Little A wants to know: how many different distribution plans can successfully allocate all $$$S$$$ crystals while satisfying the capacity limits of all pillars?

Since the number of valid plans might be extremely large, you only need to output the answer modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

For each test case: The first line contains two integers $$$N$$$ and $$$S$$$ ($$$1 \le N \le 15$$$, $$$1 \le S \le 10^9$$$) — the number of pillars and the total number of starlight crystals.

The second line contains $$$N$$$ integers $$$L_1, L_2, \dots, L_N$$$ ($$$0 \le L_i \le 10^9$$$) — the maximum capacity of each pillar.

Output

For each test case, output a single integer on a new line, representing the number of valid distribution plans modulo $$$10^9+7$$$.

Example
Input
3
2 5
3 3
3 4
1 2 3
15 1000000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
2
5
0
Note

In the first example, there are 2 pillars and 5 crystals to distribute. Both pillars have a capacity limit of 3. There are only two valid distribution plans:

  1. Place 2 crystals in the first pillar, and 3 in the second.
  2. Place 3 crystals in the first pillar, and 2 in the second.
Output 2.

In the second example, there are 3 pillars and 4 crystals to distribute. The capacity limits are 1, 2, and 3, respectively.

There are three valid distribution plans:

  1. $$$(0, 1, 3)$$$
  2. $$$(1, 0, 3)$$$
  3. $$$(1, 1, 2)$$$
  4. $$$(1, 2, 1)$$$
  5. $$$(0, 2, 2)$$$

Output 5.

In the third example, the 15 pillars can hold at most 1 crystal each, meaning they can hold a maximum of 15 crystals in total. It is impossible to distribute 1000000000 crystals. The number of valid plans is 0.