题目描述

一个长度为 $n$ 的大数，用 $S_1S_2S_3 \ldots 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} \ldots S_{r_1}$ 与 $S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots 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_i}_1$、${r_i}_1$、${l_i}_2$、${r_i}_2$，分别表示该限制条件对应的两个区间。

输出格式

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

4 2
1 2 3 4
3 3 3 3

90

数据范围与提示

$ 1 \leq n \leq 10 ^ 5, 1 \leq m \leq 10 ^ 5, 1 \leq {l_i}_1, {r_i}_1, {l_i}_2, {r_i}_2 \leq n $ 并且保证 ${r_i}_1 - {l_i}_1 = {r_i}_2 - {l_i}_2$。