#P3295. [SCOI2016] 萌萌哒

[SCOI2016] 萌萌哒

题目描述

一个长度为 nn 的大数,用 S1S2S3SnS_1S_2S_3 \cdots S_n表示,其中 SiS_i 表示数的第 ii 位, 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} \cdots S_{r_1}Sl2Sl2+1Sl2+2Sr2S_{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 ,那么 123123123123351351351351 均满足条件,但是 1201212012131141131141 不满足条件,前者数的长度不为 66 ,后者第二位与第五位不同。问满足以上所有条件的数有多少个。

输入格式

第一行两个数 nnmm,分别表示大数的长度,以及限制条件的个数。

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

1n1051\le n\le 10^51m1051\le m\le 10^51li1,ri1,li2,ri2n1\le l_{i_1},r_{i_1},{l_{i_2}},r_{i_2}\le n ;并且保证 ri1li1=ri2li2 r_{i_1}-l_{i_1}=r_{i_2}-l_{i_2}

输出格式

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

4 2
1 2 3 4
3 3 3 3
90