A large number of length $n$ is represented as $S_1S_2S_3...S_n$, where $S_i$ represents the $i$-th digit of the number, and $S_1$ is the most significant digit.

You are given some constraints. Each constraint is represented by four numbers $l_1, r_1, l_2, r_2$, which define two intervals of the same length. This means the substring $S_{l_1}S_{l_1+1}S_{l_1+2}...S_{r_1}$ must be identical to the substring $S_{l_2}S_{l_2+1}S_{l_2+2}...S_{r_2}$.

For example, when $n = 6$, if a constraint is $l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6$, then $123123$ and $351351$ satisfy the condition, but $12012$ and $131141$ do not. The former does not have a length of $6$, and in the latter, the second digit is different from the fifth digit.

Find the number of such integers that satisfy all the given conditions.

Input

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

The next $m$ lines each contain four integers $l_1, r_1, l_2, r_2$, representing the two intervals for each constraint.

Output

A single integer representing the number of large numbers of length $n$ that satisfy all conditions. Since the answer may be very large, output the result modulo $10^9 + 7$.

Examples

Input 1

4 2
1 2 3 4
3 3 3 3

Output 1

90

Constraints

• $30\%$ of the data: $1 \le n \le 2000, 1 \le m \le 2000$
• $100\%$ of the data: $1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le l_1, r_1, l_2, r_2 \le n$
• It is guaranteed that $r_1 - l_1 = r_2 - l_2$