hackercupai/hackercup huggingface dataset:
A quiet evening has set over a residential area. As families sit down for
supper in the safety of their homes, a calm atmosphere permeates the outside
air. The neighborhood feels truly at peace, separated from the frenzy of the
rest of the world. Also, a bunch of zombies have just risen out of the ground
and want to eat everybody.

The neighborhood has **N** yards in a row, numbered from 1 to **N**. There are
also **N**-1 fences, one between each pair of adjacent yards. The fence
between yards _i_ and _i_+1 has an unknown integral height drawn uniformly at
random from the inclusive interval [**Ai**, **Bi**]. In other words, the _i_th
fence has **Bi** \- **Ai** \+ 1 possible heights, each of which is equally
likely.

**M** hungry zombies are also present, with the _i_th of them initially in yard **Yi**. Fortunately for the zombies, they might not be stopped by the surrounding fences so easily. The _i_th zombie has the ability to climb over any fence with a height of at most **Hi**. It may repeatedly move from its current yard to an adjacent one, as long as the fence between the yards is no taller than **Hi**. Multiple zombies may start in the same yard, and multiple zombies may occupy the same yard at any point.

A yard is considered "safe" if it's impossible for any zombies to ever reach
it. Determine the probability that at least one of the **N** yards is safe.
Let this probability be represented as a quotient of integers _p_/_q_ in
lowest terms. Output the value of this quotient modulo 1,000,000,007 — in
other words, output the unique integer _x_ such that 0 ≤ _x_ < 1,000,000,007
and _p_ = _x_*_q_ (modulo 1,000,000,007).

### Input

Input begins with an integer **T**, the number of neighborhoods. For each
neighborhood, there is first a line containing the space-separated integers
**N** and **M**. Then, **N-1** lines follow. The _i_th of these lines contains
the space-separated integers **Ai** and **Bi**. Then, **M** lines follow. The
_i_th of these lines contains the space-separated integers **Yi** and **Hi**.

### Output

For the _i_th neighborhood, print a line containing "Case #_i_: " followed by
1 integer, the probability that at least one of the yards is safe, expressed
as a quotient of integers modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 75
1 ≤ **N** ≤ 3,000
1 ≤ **M** ≤ 3,000
1 ≤ **Ai** ≤ **Bi** ≤ 1,000,000
1 ≤ **Yi** ≤ **N**
1 ≤ **Hi** ≤ 1,000,000

### Explanation of Sample

In the first case, if the height of the single fence is 100, then the zombie
in yard 1 will be able to climb over it to reach yard 2, meaning that no yards
will be safe. Otherwise, if the fence's height is 101, then yard 2 will be
safe. Therefore, the probability that at least one of the yards is safe is 1/2
= 500000004 (modulo 1,000,000,007).

In the second case, in order for yard 2 to be safe from both surrounding
zombies, the first fence's height must be either 3 or 4, and the second
fence's height must be 4. The probability of this occurring is 2/4 * 1/4 = 1/8
= 125000001 (modulo 1,000,000,007).

In the third case, the probability of at least one yard being safe is 2/3 =
666666672 (modulo 1,000,000,007).