나비넥타이 세기

정점이 $2N$개인 이분 그래프가 있다. 그중 $N$개는 천장에 매달려 있고, 나머지 $N$개는 바닥에 붙어 있다. 천장의 정점과 바닥의 정점에는 각각 1번부터 $N$번까지 번호가 붙어 있다.

천장과 바닥은 $M$개의 사다리꼴로 이어진다. 각 사다리꼴은 천장에서 차지하는 구간 $[s_x, e_x]$와 바닥에서 차지하는 구간 $[s_y, e_y]$로 나타낸다. 천장의 정점 $i$와 바닥의 정점 $j$는 $s_x \le i \le e_x$와 $s_y \le j \le e_y$를 모두 만족하는 사다리꼴이 하나라도 있으면 간선으로 이어진다. 같은 간선을 여러 사다리꼴이 덮어도 간선은 하나로 센다.

이 그래프에서 길이가 4인 단순 사이클을 나비넥타이라고 한다. 천장의 서로 다른 두 정점 $i_1$, $i_2$와 바닥의 서로 다른 두 정점 $j_1$, $j_2$에 대해 간선 $(i_1, j_1)$, $(i_1, j_2)$, $(i_2, j_1)$, $(i_2, j_2)$가 모두 있으면 나비넥타이가 하나 만들어진다. 두 나비넥타이는 이루는 간선 집합에서 다른 원소가 하나라도 있으면 서로 다르다.

그래프의 모양이 주어질 때, 나비넥타이의 개수를 세는 프로그램을 작성하라.

위아래에 정점이 9개씩 있고 사다리꼴이 두 개인 그래프다. 점선은 이 그래프에서 찾을 수 있는 나비넥타이 하나를 나타낸다.

첫째 줄에 $N$ ($1 \le N \le 10^9$)과 $M$ ($0 \le M \le 1000$)이 공백을 사이에 두고 주어진다. 그래프의 정점이 $2N$개이고 사다리꼴이 $M$개라는 뜻이다.

다음 $M$개의 줄에 사다리꼴이 한 줄에 하나씩 $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$).

나비넥타이의 개수를 $10^9 + 7$로 나눈 나머지를 첫째 줄에 출력한다.