Description

An $n$-digit number is denoted by $S_1 S_2 S_3 \cdots S_n$, where $S_i$ is the $i$-th digit and $S_1$ is the most significant digit. You are given several constraints. Each constraint is given by four integers $l_1, r_1, l_2, r_2$, meaning two intervals of the same length, and it requires the substrings $S_{l_1} S_{l_1+1} S_{l_1+2} \cdots S_{r_1}$ and $S_{l_2} S_{l_2+1} S_{l_2+2} \cdots S_{r_2}$ to be exactly the same.

For example, when $n=6$ and there is a constraint $l_1=1, r_1=3, l_2=4, r_2=6$, then 123123 and 351351 both satisfy the condition, but 12012 and 131141 do not. The former is not of length $6$, and in the latter the second and fifth digits differ. Find how many numbers satisfy all the given conditions.

Input Format

The first line contains two integers $n$ and $m$, representing the length of the number and the number of constraints.

Each of the next $m$ lines contains four integers $l_{i_1}, r_{i_1}, {l_{i_2}}, r_{i_2}$ on the $i$-th line, representing the two intervals for that constraint.

$1 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le l_{i_1}, r_{i_1}, {l_{i_2}}, r_{i_2} \le n$, and it is guaranteed that $r_{i_1} - l_{i_1} = r_{i_2} - l_{i_2}$.

Output Format

Output a single integer, the number of $n$-digit numbers that satisfy all the constraints. Since the answer can be large, output it modulo $10^9+7$.

4 2
1 2 3 4
3 3 3 3

90

Hint

Translated by ChatGPT 5