Sweet Corn Rectangles

Farmer John has a large square field with integer coordinates from (0,0) to (N-1, N-1). In his field, there are several double‐headed sprinklers placed at some integer coordinates. A sprinkler located at (i,j) waters all points (x,y) satisfying

\( N \ge x \ge i \text{ and } N \ge y \ge j \),

and fertilizes all points satisfying

\( 0 \le x \le i \text{ and } 0 \le y \le j \).

Farmer John wishes to choose an axis–aligned rectangle with positive area (its corners have integer coordinates), such that every point inside the rectangle is both watered and fertilized. In other words, if the rectangle is defined by its lower–left corner (x₁,y₁) and upper–right corner (x₂,y₂) (with x₁ < x₂ and y₁ < y₂), then there must exist at least one sprinkler at some (a,b) with

\( a \le x_1 \text{ and } b \le y_1 \) (which waters the rectangle),

and at least one sprinkler at some (c,d) with

\( c \ge x_2 \text{ and } d \ge y_2 \) (which fertilizes the rectangle).

Compute the number of such valid rectangles, and output the answer modulo \(10^9+7\).

inputFormat

The first line contains two integers N and M — the size parameter of the field, and the number of sprinklers, respectively. The field has integer coordinates from 0 to N-1 in each dimension. The following M lines each contain two integers i and j representing the coordinates of a sprinkler.

outputFormat

Output a single integer — the number of valid rectangles of positive area that satisfy the conditions, modulo \(10^9+7\).

sample

3 2
0 0
2 2

9