题目描述

一个长度为 $n$ 的大数，用 $s_1s_2s_3 \dots s_n$表示，其中 $s_i$ 表示数的第i，$s_1$是数的最高位，
告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_{2}$，即两个长度相同的区间，表示子串 $s_{l_1}s_{l_1+1}s_{l_1+2} \dots s_{r_1}$ 与 $s_{l_2}s_{l_2+1}s_{l_2+2} \dots s_{r_2}$ 完全相同。
比如 $n=6$ 时，某限制条件 $l_1=1,r_1=3,l_2=4,r_2=6$，
那么 $123123,351351$ 均满足条件，但是 $12012,131141$ 不满足条件，前者数的长度不为 $6$，后者第二位与第五位不同。
问满足以上所有条件的数有多少个。

输入格式

第一行两个数 $n$ 和 $m$，分别表示大数的长度，以及限制条件的个数。
接下来 $m$ 行，对于第 $i$ 行，有 $4$ 个数 $l_{i1},r_{i1},l_{i2},r_{i2}$，分别表示该限制条件对应的两个区间。

输出格式

一个数，表示满足所有条件且长度为 $n$ 的大数的个数，答案可能很大，因此输出答案模 $10^9+7$ 的结果即可。

4 2
1 2 3 4
3 3 3 3

90

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq m \leq 10^5$，$1 \leq l_{i1},r_{i1},l_{i2},r_{i2} \leq n$，保证 $r_{i1}-l_{i1}=r_{i2}-l_{i2}$。