题目描述

一个长度为 $ n $ 的大数，用 $ S_1S_2S_3 \ldots S_n $表示，其中 $ S_i $ 表示数的第 $ i $ 位，$ S_1 $ 是数的最高位，告诉你一些限制条件，每个条件表示为四个数 $ (l_1, r_1, l_2, r2) $，即两个长度相同的区间，表示子串 $ S{l1}S{l1 + 1}S{l1 + 2} \ldots S{r1} $ 与 $ S{l2}S{l2 + 1}S{l2 + 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 $ 的结果即可。

样例

input

4 2
1 2 3 4
3 3 3 3

output

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 $。