Farmer John 有 $N$ 头奶牛（$2 \leq N \leq 5\cdot 10^6$），他试图利用奶牛的懒惰来对一个长度为 $N$ 的非负整数数组 $A$ 进行排序。他有很多沉重的箱子，于是他让奶牛们排成一队，奶牛 $i+1$ 在奶牛 $i$ 后面，并给奶牛 $i$ 分配了 $a_i$ 个箱子（$0\le a_i$）。

奶牛天生懒惰，总是想把工作推给别人。从奶牛 $1$ 到 $N-1$ 依次进行，每头奶牛都会观察身后的奶牛。如果奶牛 $i$ 手中的箱子数量严格多于奶牛 $i+1$，奶牛 $i$ 会认为这“不公平”，并将其中的一个箱子交给奶牛 $i+1$。这个过程会一直重复，直到每头奶牛都感到满意为止。

Farmer John 随后会记录每头奶牛 $i$ 持有的箱子数量 $b_i$，并由此组成数组 $B$。如果 $B = sorted(A)$，那么 Farmer John 就会感到满意。不幸的是，Farmer John 只记得 $A$ 中 $Q$ 个值（$2 \leq Q \leq \min(N, 100)$）。幸运的是，这些值包括了他最初分配给第一头和最后一头奶牛的箱子数量。FJ 记得的每个值都以 $c_i \; v_i$ 的形式给出，表示 $a_{c_i}=v_i$（$1 \leq c_i \leq N$，$1\le v_i\le 10^9$）。请计算有多少种填充缺失值的方法，使得他最终感到满意，结果对 $10^9+7$ 取模。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $Q$，分别表示奶牛的数量和已知值的数量。

接下来的 $Q$ 行，每行包含两个空格分隔的整数 $c_i \; v_i$，表示第 $c_i$ 头奶牛最初持有 $v_i$ 个箱子。保证 $c_1 = 1$，$c_Q = N$，且 $c_i < c_{i+1}$（奶牛的编号严格递增）。

输出格式

输出在奶牛完成懒惰排序后，使得 Farmer John 满意的 $a_i$ 赋值方案数，结果对 $10^9+7$ 取模。保证至少存在一种合法的赋值方案。

样例

样例输入 1

3 2
1 3
3 2

样例输出 1

2

样例输入 2

6 3
1 1
3 3
6 5

样例输出 2

89

数据范围

• 输入 3-4：$N,v_i\le 100$
• 输入 5-6：$N\le 100$ 且 $v_i \leq 10^6$
• 输入 7-9：$N \leq 2\cdot 10^5$ 且 $v_i \le 10^6$
• 输入 10-12：$N \leq 2\cdot 10^5$
• 输入 13-15：无额外限制。