2018年1月USACO美国计算机奥赛白金级题3

USACO 2018 January Contest, Platinum Problem 3. Sprinklers

2018年1月USACO美国计算机奥赛白金级题3

Farmer John has a large field, and he is thinking of planting sweet corn in some part of it. After surveying his field, FJ found that it forms an (N1)×(N1)(N−1)×(N−1) square. The southwest corner is at coordinates (0,0)(0,0), and the northeast corner is at (N1,N1)(N−1,N−1).

At some integer coordinates there are double-headed sprinklers, each one sprinkling both water and fertilizer. A double-heading sprinkler at coordinates (i,j)(i,j) sprinkles water on the part of the field north and east of it, and sprinkles fertilizer on the part of the field south and west of it. Formally, it waters all real coordinates (x,y)(x,y) for which NxiN≥x≥i and NyjN≥y≥j, and it fertilizes all real coordinates (x,y)(x,y) for which 0xi0≤x≤i and 0yj0≤y≤j.

Farmer John wants to plant sweet corn in some axis-aligned rectangle in his field with integer-valued corner coordinates. However, for the sweet corn to grow, all points in 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 wouldn’t 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, output the remainder of this number modulo 109+7109+7.

INPUT FORMAT (file sprinklers.in):

The first line of the input consists of a single integer NN, the size of the field (1N1051≤N≤105).The next NN lines each contain two space-separated integers. If these integers are ii and jj, where 0i,jN10≤i,j≤N−1, they denote a sprinkler located at (i,j)(i,j).

It is guaranteed that there is exactly one sprinkler in each column and exactly one sprinkler in each row. That is, no two sprinklers have the same xx-coordinate, and no two sprinklers have the same yy-coordinate.

OUTPUT FORMAT (file sprinklers.out):

The output should consist of a single integer: the number of rectangles of positive area which are fully watered and fully fertilized, modulo 109+7109+7.

SAMPLE INPUT:

5
0 4
1 1
2 2
3 0
4 3

SAMPLE OUTPUT:

21

Problem credits: Dhruv Rohatgi