萌萌哒

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

一个长度为 $n$ 的大数，用 $S_1S_2S_3\cdots S_n$ 表示，其中 $S_i$ 表示数的第 $i$ 位，$S_1$ 是数的最高位。现在给出若干限制条件。每个条件由四个整数 $l_1,r_1,l_2,r_2$ 表示，两个区间长度相同，并要求子串 $S_{l_1}\cdots S_{r_1}$ 与 $S_{l_2}\cdots S_{r_2}$ 完全相同。

求满足所有限制条件且长度为 $n$ 的大数个数。

输入格式

第一行包含两个整数 $n,m$，分别表示大数长度和限制条件数。

接下来 $m$ 行，每行包含四个整数 $l_1,r_1,l_2,r_2$，描述一条限制。

输出格式

输出满足条件的大数个数对 $10^9+7$ 取模后的结果。

样例输入 1

4 2
1 2 3 4
3 3 3 3

样例输出 1

90

数据范围

$1\le n,m\le 10^5$，$1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$，且 $r_1-l_1=r_2-l_2$。