bzoj#P4569. [SCOI2016] 萌萌哒

[SCOI2016] 萌萌哒

题目描述

一个长度为 nn 的大数,用 s1s2s3sns_1s_2s_3 \dots s_n表示,其中 sis_i 表示数的第i,s1s_1是数的最高位,
告诉你一些限制条件,每个条件表示为四个数,l1,r1,l2,r2l_1,r_1,l_2,r_{2},即两个长度相同的区间,表示子串 sl1sl1+1sl1+2sr1s_{l_1}s_{l_1+1}s_{l_1+2} \dots s_{r_1}sl2sl2+1sl2+2sr2s_{l_2}s_{l_2+1}s_{l_2+2} \dots 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
那么 123123,351351123123,351351 均满足条件,但是 12012,13114112012,131141 不满足条件,前者数的长度不为 66,后者第二位与第五位不同。
问满足以上所有条件的数有多少个。

输入格式

第一行两个数 nnmm,分别表示大数的长度,以及限制条件的个数。
接下来 mm 行,对于第 ii 行,有 44 个数 li1,ri1,li2,ri2l_{i1},r_{i1},l_{i2},r_{i2},分别表示该限制条件对应的两个区间。

输出格式

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

4 2
1 2 3 4
3 3 3 3
90

数据规模与约定

对于 100%100\% 的数据,1n1051 \leq n \leq 10^51m1051 \leq m \leq 10^51li1,ri1,li2,ri2n1 \leq l_{i1},r_{i1},l_{i2},r_{i2} \leq n,保证 ri1li1=ri2li2r_{i1}-l_{i1}=r_{i2}-l_{i2}