Sprinklers#10428
Farmer John has a large field, and he is thinking of planting sweet corn in part of it. After surveying the field, he has found that it forms an (n - 1) \times (n - 1) square. The southwest corner is at coordinates , and the northeast corner is at (n - 1, n - 1).
At some integer points there are double-headed sprinklers, each of which sprinkles both water and fertilizer. A double-headed sprinkler at coordinates waters the part of the field to the north and east of it and fertilizes the part of the field to the south and west of it. Formally, it waters all real points such that i \le x \le n - 1 and j \le y \le n - 1, and it fertilizes all real points such that 0 \le x \le i and 0 \le y \le j.
Farmer John wants to plant sweet corn in an axis-aligned rectangle in his field whose corners have integer coordinates. However, for the sweet corn to grow, every point of the rectangle must be both watered and fertilized by the double-headed sprinklers. And of course, the rectangle must have positive area, or Farmer John would not be able to grow any corn in it!
Help Farmer John determine the number of rectangles of positive area in which he could grow sweet corn. Since this number may be large, print it modulo 10^9 + 7.
The first line contains one integer n~(1 \le n \le 10^5), the size of the field. Each of the next lines contains two integers and j~(0 \le i, j \le n - 1), denoting a sprinkler located at .
It is guaranteed that there is exactly one sprinkler in each column and exactly one sprinkler in each row. That is, no two sprinklers share the same -coordinate, and no two sprinklers share the same -coordinate.
Print one integer: the number of rectangles of positive area that are fully watered and fully fertilized, modulo 10^9 + 7.
Example 1