题目描述

Farmer John 养了 $N$（$2 \le N \le 5 \cdot 10^6$）头牛，他想利用这些牛的懒惰天性来排序一个长度为 $N$ 的非负整数数组 $A$。他手头有许多沉重的箱子，于是他把牛排成一列，从前往后依次编号为 $1$ 到 $N$，其中第 $i+1$ 头牛站在第 $i$ 头牛后面，然后给第 $i$ 头牛分配 $a_i$（$0 \le a_i$）个箱子。

牛天生懒惰，总想把活儿推给别人。从第 $1$ 头牛到第 $N-1$ 头牛，每头牛都会回头看看身后的牛。如果第 $i$ 头牛的箱子数量严格多于第 $i+1$ 头牛，它会觉得这不公平，于是把自己的一只箱子递给后面的牛。这个过程会一直重复，直到每头牛都满意为止。

之后，Farmer John 会记录每头牛 $i$ 最终持有的箱子数量 $b_i$，并以此组成数组 $B$。如果 $B = \text{sorted}(A)$，也就是数组 $A$ 的升序排列，Farmer John 就会很开心。可惜的是，他只记得数组 $A$ 中的 $Q$（$2 \le Q \le \min(N, 100)$）个值，不过幸运的是，这些值包括他打算给第一头牛和最后一头牛的箱子数量。他记得的每个值以 $c_i\; v_i$ 的形式给出，表示 $a_{c_i} = v_i$（$1 \le c_i \le 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 开心的不同赋值方式数量，对 $10^9 + 7$ 取模。保证至少存在一种有效赋值。

3 2
1 3
3 2

2

6 3
1 1
3 3
6 5

89

测试点性质

• 测试点 3-4: $N,v_i\leq 100$。
• 测试点 5-6: $N\leq 100$ 且 $v_i\leq 10^6$。
• 测试点 7-9: $N\leq 2\times 10^5$ 且 $v_i\leq 10^6$.
• 测试点 10-12: $N\leq 2\times 10^5$。
• 测试点 13-15: 没有额外限制。

供题：Suhas Nagar