#2014. 「SCOI2016」萌萌哒

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

输入格式

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

输出格式

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