Counting Bow Ties

A bipartite graph has $2N$ vertices. $N$ of them hang from the ceiling and the other $N$ sit on the floor. The ceiling vertices are numbered 1 through $N$, and the floor vertices are numbered the same way.

$M$ trapezoids connect the ceiling to the floor. Each trapezoid is given by the segment $[s_x, e_x]$ it occupies on the ceiling and the segment $[s_y, e_y]$ it occupies on the floor. Ceiling vertex $i$ and floor vertex $j$ are joined by an edge when at least one trapezoid satisfies both $s_x \le i \le e_x$ and $s_y \le j \le e_y$. When several trapezoids cover the same edge, the edge still counts once.

A simple cycle of length 4 in this graph is called a bow tie. Two different ceiling vertices $i_1$, $i_2$ and two different floor vertices $j_1$, $j_2$ form one bow tie when all four edges $(i_1, j_1)$, $(i_1, j_2)$, $(i_2, j_1)$, $(i_2, j_2)$ are present. Two bow ties are different when their edge sets differ in at least one element.

Given the shape of the graph, count the bow ties.

A graph with 9 vertices on each side and two trapezoids. The dashed lines mark one bow tie in it.

The first line contains $N$ ($1 \le N \le 10^9$) and $M$ ($0 \le M \le 1000$), separated by a space. The graph has $2N$ vertices and there are $M$ trapezoids.

Each of the next $M$ lines contains one trapezoid in the form $s_x$ $e_x$ $s_y$ $e_y$ ($1 \le s_x \le e_x \le N$, $1 \le s_y \le e_y \le N$).

Print the number of bow ties modulo $10^9 + 7$.