题目描述

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 $(N-1) \times (N-1)$ square. The southwest corner is at coordinates $(0,0)$, and the northeast corner is at $(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)$ 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)$ for which $N \geq x \geq i$ and $N \geq y \geq j$, and it fertilizes all real coordinates $(x,y)$ for which $0 \leq x \leq i$ and $0 \leq y \leq 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 $10^9 + 7$.

输入格式

The first line of the input consists of a single integer $N$, the size of the field ($1 \leq N \leq 10^5$).

The next $N$ lines each contain two space-separated integers. If these integers are $i$ and $j$, where $0 \leq i,j \leq N-1$, they denote a sprinkler located at $(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 $x$-coordinate, and no two sprinklers have the same $y$-coordinate.

输出格式

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

题目大意

农夫约翰有块田，这块田可视为一个 $N×N$ 的正方形网格。西南角为 $(0,0)$ ，东北角为 $(N-1, N-1)$ 。
在某些格子中有双头喷头，每一个都能够同时喷洒水和肥料。一个位于 $(i,j)$ 的双头喷头会

• 将水洒在所有满足 $N≥x≥i,$ $N≥y≥j$ 的格子 $(x,y)$ 上；
• 将肥料洒在所有满足 $0≤x≤i$ 和 $0≤y≤j$ 的格子 $(x,y)$ 上。

农民约翰想在这块田里切割出一个矩形种甜玉米。矩形的边不能把格子切开。矩形内的所有格子都必须能由双头喷头灌溉和施肥。
求切割矩形的方案数。由于这个数字可能很大，所以输出对 $10^9+7$ 取模。 输入

第一行包含一个整数 $N$ ，表示农场的大小。
接下来的 $N$ 行，每行有两个由空格分隔的整数 $i, j$ 。这表示有一个双头喷头位于 $(i, j)$ 。
保证每列都有一台喷头，每排正好有一台喷头。换句话说，没有两个喷头有相同的横坐标或纵坐标。 输出

输出包含一行，表示方案数，对 $10^9+7$ 取模。

5
0 4
1 1
2 2
3 0
4 3

21