A6009. 「USACO 2025 US Open Platinum」Lazy Sort

**题目译自 [USACO 2025 US Open Contest, Platinum](http://usaco.org/index.php?page=open25results) Problem 2. [Lazy Sort](https://usaco.org/index.php?page=viewproblem2&cpid=1525)**

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$ 取模。保证至少存在一种有效赋值。