hackercupai/hackercup huggingface dataset:
Today, Mr. Fox is taking it easy by playing with some blocks in a 2D world.
Each block is an inch-by-inch square, and there are **N** stacks of blocks in
a row, with the **i**th stack having **Hi** blocks. For example, if **N**=6
and **H**={3, 1, 5, 4, 1, 6}, then the collection of blocks looks like this
(where an "X" denotes a block):

.....X
..X..X
..XX.X
X.XX.X
X.XX.X
XXXXXX

Ever curious, Mr. Fox would like to answer **Q** questions about his blocks
(without actually modifying them), the **i**th one being as follows:

"If I were to consider only the stacks from **Ai** to **Bi** inclusive,
getting rid of all of the other blocks, how many square inches of water would
my block structure be able to hold?"

As one might imagine, a given square inch can hold water if it doesn't contain
a block itself, but there is a block both somewhere to its left and somewhere
to its right at the same height. For example, if you were to take **Ai**=2 and
**Bi**=6, you would be left with the following block structure to consider
(where an "*" denotes an inch-by-inch square which can hold water):

....X
.X**X
.XX*X
.XX*X
.XX*X
XXXXX

### Constraints

1 ≤ **T** ≤ 20
1 ≤ **N** ≤ 300,000
1 ≤ **Q** ≤ 300,000
1 ≤ **Hi** ≤ 109
1 ≤ **Ai** ≤ **Bi** ≤ **N**

### Input

Input begins with an integer **T**, the number of block structures Mr. Fox
has. For each structure, there is first a line containing the space-separated
integers **N** and **Q**. The next line contains the space-separated integers
**Hi**. Then follow **Q** lines, the **i**th of which contains the space-
separated integers **Ai** and **Bi**.

### Output

For the **i**th structure, print a line containing "Case #**i**: " followed by
the sum of the answers to the **Q** questions modulo 109+7.

### Explanation of Sample

In the first case, we consider prefixes of the block structure. The answers to
the queries are 0, 0, 0, 0, 0, 5, 5, 7, 7, 18, 18 for a total of 60.