#P1097. 「SCOI2016」萌萌哒

「SCOI2016」萌萌哒

题目描述

一个长度为 n n 的大数,用 S1S2S3Sn S_1S_2S_3 \ldots S_n 表示,其中 Si S_i 表示数的第 i i 位,S1 S_1 是数的最高位,告诉你一些限制条件,每个条件表示为四个数 (l1,r1,l2,r2) (l_1, r_1, l_2, r_2) ,即两个长度相同的区间,表示子串 Sl1Sl1+1Sl1+2Sr1 S_{l_1}S_{l_1 + 1}S_{l_1 + 2} \ldots S_{r_1} Sl2Sl2+1Sl2+2Sr2 S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots S_{r_2} 完全相同。

比如 n=6 n = 6 时,某限制条件 (l1=1,r1=3,l2=4,r2=6) (l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6) ,那么 123123 123123 351351 351351 均满足条件,但是 12012 12012 131141 131141 不满足条件,前者数的长度不为 6 6 ,后者第二位与第五位不同。问满足以上所有条件的数有多少个。

输入格式

第一行两个数 n n m m ,分别表示大数的长度,以及限制条件的个数。
接下来 m m 行,对于第 i i 行,有 4 4 个数 li1 {l_i}_1 ri1 {r_i}_1 li2 {l_i}_2 ri2 {r_i}_2 ,分别表示该限制条件对应的两个区间。

输出格式

一个数,表示满足所有条件且长度为 n n 的大数的个数,答案可能很大,因此输出答案模 109+7 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 $ 并且保证 ri1li1=ri2li2 {r_i}_1 - {l_i}_1 = {r_i}_2 - {l_i}_2