Counting Fancy Rectangles in a Segmented Fence

Balázs is known to have the prettiest fence in town. The fence consists of N rectangular parts placed consecutively so that adjacent parts are touching. The i-th part of the fence has height h_i and width w_i. A fancy rectangle is defined as an axis‐aligned rectangle satisfying the following conditions:

• All its sides are horizontal or vertical with integer lengths.
• The vertical distance between the rectangle and the ground is an integer.
• The horizontal distance between the rectangle and the left side of the first fence part is an integer.
• The rectangle is completely contained within the fence.

In other words, if we view the fence as a histogram with a total width $$L=\sum_{i=1}^{N}w_i,$$ and define the fence profile so that for any integer horizontal coordinate x the fence has height given by H(x) (with H(x)=h_i for x in the interval corresponding to part i), then any fancy rectangle is an axis‐aligned rectangle whose bottom and left edges lie at integer distances from the ground and the left side, respectively, and whose top edge does not exceed H(x) for every x within its horizontal span.

Your task is to count the total number of fancy rectangles. For any chosen horizontal boundaries with integer coordinates x₁ and x₂ (with 0 \le x₁ < x₂ \le L), the maximal allowed top edge is $$m=\min_{x\in[x_1,x_2]}H(x).$$ For that fixed horizontal span, the number of ways to choose the vertical sides is equal to the number of pairs of integers y₁, y₂ satisfying $$0\le y_1<y_2\le m,$$ which equals $$\frac{m(m+1)}{2}.$$ Thus, the final answer is the sum over all valid horizontal intervals of $$\frac{m(m+1)}{2},$$ computed modulo \(10^9+7\).

inputFormat

The first line contains an integer N (the number of fence parts). Each of the next N lines contains two integers h_i and w_i representing the height and width of the i-th fence part respectively.

outputFormat

Output a single integer – the total number of fancy rectangles modulo 10^9+7.

sample

1
3 4

60