题目描述
一个长度为 n 的大数,用 s1s2s3…sn表示,其中 si 表示数的第i,s1是数的最高位,
告诉你一些限制条件,每个条件表示为四个数,l1,r1,l2,r2,即两个长度相同的区间,表示子串 sl1sl1+1sl1+2…sr1 与 sl2sl2+1sl2+2…sr2 完全相同。
比如 n=6 时,某限制条件 l1=1,r1=3,l2=4,r2=6,
那么 123123,351351 均满足条件,但是 12012,131141 不满足条件,前者数的长度不为 6,后者第二位与第五位不同。
问满足以上所有条件的数有多少个。
输入格式
第一行两个数 n 和 m,分别表示大数的长度,以及限制条件的个数。
接下来 m 行,对于第 i 行,有 4 个数 li1,ri1,li2,ri2,分别表示该限制条件对应的两个区间。
输出格式
一个数,表示满足所有条件且长度为 n 的大数的个数,答案可能很大,因此输出答案模 109+7 的结果即可。
4 2
1 2 3 4
3 3 3 3
90
数据规模与约定
对于 100% 的数据,1≤n≤105,1≤m≤105,1≤li1,ri1,li2,ri2≤n,保证 ri1−li1=ri2−li2。