该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
样例下载
题目描述
一个 n 位的大整数,用 S1S2S3…Sn表示,其中 Si 表示数的左数第 i 位, S1 是数的最高位。显然 S1=0。
告诉你 m 个限制条件,每个条件表示为四个数,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 的大数的个数,答案可能很大,输出答案 mod 109+7。
输入样例
4 2
1 2 3 4
3 3 3 3
输出样例
90
数据范围
1≤n,m≤105,1≤li1,ri1,li2,ri2≤n ;输入数据保证 li1≤ri1 且 li2≤ri2 且 ri1−li1=ri2−li2 。