Problem 2. Lazy Sort

USACO 2025 US Open Contest, Platinum

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)$）。幸运的是，这些值中包含他打算给第一头和最后一头奶牛的箱子数量。Farmer John 记得的每一个值以 $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}$（输入的奶牛编号是严格递增的）。

输出格式（输出至终端 / 标准输出）：

输出值 $a_i$ 可以被分配的不同方案的数量，以使得 Farmer John 在奶牛进行懒惰排序后会高兴，答案对 $10^9+7$ 取模。输入保证存在至少一种合法的分配方案。

输入样例：

3 2
1 3
3 2

输出样例：

2

在这个例子中，Farmer John 记住了数组两端的值。数组 $[3,2,2]$ 和 $[3,3,2]$ 是在懒惰排序结束时会让 Farmer John 感到高兴的合法数组。

输入样例：

6 3
1 1
3 3
6 5

输出样例：

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：没有额外限制。

供题：Suhas Nagar