hackercupai/hackercup huggingface dataset:
**N** groups of people are heading to the beach today! The _i_th group is bringing a circular umbrella with a radius **Ri** meters.

The beach has **M** acceptable points at which umbrellas may be screwed into
the sand, arranged in a line with 1 meter between each adjacent pair of
points. Each group of people will choose one such point at which to position
the center of their umbrella.

Of course, it's no good if any pair of umbrellas collide (that is, if the
intersection of their circles has a positive area). The **N** groups will work
together to place their umbrellas such that this doesn't happen. However,
they're wondering in how many distinct ways that can be accomplished. Two
arrangements are considered to be distinct if they involve at least one group
placing their umbrella in a different spot. As this quantity may be very
large, they're only interested in its value modulo 1,000,000,007.

Note that it might be impossible for all of the groups to validly place their
umbrellas, yielding an answer of 0.

### Input

Input begins with an integer **T**, the number of days the beach is open. For
each day, there is first a line containing two space-separated integers, **N**
and **M**. Then, **N** lines follow, the _i_th of which contains a single
integer, **Ri**.

### Output

For the _i_th day, print a line containing "Case #**i**: " followed by the
number of valid umbrella arrangements, modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 100
1 ≤ **N** ≤ 2,000
1 ≤ **M** ≤ 1,000,000,000
1 ≤ **Ri** ≤ 2,000

### Explanation of Sample

In the second case there are six possibilities. If the radius-1 umbrella is
placed at the far-left point, then the radius-2 umbrella can be placed at
either of the two right-most points. If the radius-1 umbrella is placed at the
second point from the left, then the radius-2 umbrella must be placed at the
right-most point. That's three possibilities so far, and we can mirror them to
produce three more.