题目描述

一个长度为$n$的大数，用$S_1S_2S_3...S_n$表示，其中$S_i$表示数的第$i$位，$S_1$是数的最高位，告诉你一些限制条件，每个条件表示为四个数，$l_1，r_1，l_2，r_2$，即两个长度相同的区间，表示子串$S_{l1}S_{l1+1}S_{l1+2}...S_{r1}$与$S_{l2}S_{l2+1}S_{l2+2}...S_{r2}$完全相同。 比如$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_{i1}，r_{i1}，l_{i2}，r_{i2}$，分别表示该限制条件对应的两个区间。$1≤n≤10^5，1≤m≤10^5，1≤l_{i1},r_{i1},l_{i2},r_{i2}≤n$，并且保证$r_{i1}-l_{i1}=r_{i2}-l_{i2}$。

输出

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

输入样例

4 2
1 2 3 4
3 3 3 3

输出样例

90

提示

【数据规模】 对于20%的数据，$n,m≤2000$。 对于100%的数据，$1≤n,m≤10^5$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。