#897. 数的统计

数的统计

样例下载

题目描述

一个 nn 位的大整数,用 S1S2S3…SnS_1 S_2 S_3 … S_n表示,其中 SiS_i 表示数的左数第 ii 位, S1S_1 是数的最高位。显然 S1≠0S_1 ≠ 0。

告诉你 m 个限制条件,每个条件表示为四个数,l1,r1,l2,r2l_1,r_1,l_2,r_2,即两个长度相同的区间,表示子串 Sl1Sl1+1Sl1+2⋯Sr1S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1} 与 Sl2Sl2+1Sl2+2⋯Sr2S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2} 完全相同。

比如 n=6n=6 时,某限制条件 l1=1,r1=3,l2=4,r2=6l_1=1,r_1=3,l_2=4,r_2=6 ,那么 123123123123,351351351351 均满足条件,但是 1201212012,131141131141 不满足条件,前者数的位数不为 66 ,后者第二位与第五位不同。

问:满足所有限制条件的数有多少个?

输入格式

第一行两个数 nn 和 mm,分别表示大数的位数,以及限制条件的个数。

接下来 mm 行,对于第 ii 行,有 44 个数 li1,ri1,li2,ri2l_{i_1},r_{i_1},{l_{i_2}},r_{i_2},分别表示该限制条件对应的两个区间。

输出格式

一个数,表示满足所有条件且位数为 nn 的大数的个数,答案可能很大,输出答案 mod 109+7 10^9+7 。

输入样例

4 2
1 2 3 4
3 3 3 3

输出样例

90

数据范围

1≤n,m≤1051 ≤ n, m ≤ 10^5,1≤li1,ri1,li2,ri2≤n1 ≤ l_{i_1},r_{i_1},{l_{i_2}},r_{i_2} ≤ n ;输入数据保证 li1≤ri1l_{i_1} ≤ r_{i_1} 且 li2≤ri2{l_{i_2}} ≤ r_{i_2} 且 ri1−li1=ri2−li2r_{i_1}-l_{i_1}=r_{i_2}-l_{i_2} 。