Description

农夫约翰（Farmer John）有 $N$（$2 \le N \le 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$。这个过程会一直重复，直到每头奶牛都满意为止。

然后，农夫约翰会记下每头奶牛 $i$ 持有的箱子数量 $b_i$，并用这些值创建一个数组 $B$。如果 $B = \text{sorted}(A)$（即 $A$ 排序后的结果），那么农夫约翰就会很高兴。不幸的是，农夫约翰忘记了 $A$ 中除了 $Q$（$2 \le Q \le \min(N, 100)$）个值之外的所有值。幸运的是，这些记住的值包括了他打算给第一头和最后一头奶牛的箱子数量。FJ 记住的每个值都以 $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$ 取模。

Input Format

第一行包含两个空格分隔的整数 $N$ 和 $Q$，分别代表奶牛的数量和查询（记住的值）的数量。

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

Output Format

输出可以分配 $a_i$ 值的方法数量，使得农夫约翰在奶牛执行懒惰排序后感到高兴，结果对 $10^9 + 7$ 取模。保证至少存在一种有效的分配方案。

3 2
1 3
3 2

2

6 3
1 1
3 3
6 5

89

Hint

样例 1 解释

在这个例子中，FJ 记住了数组两端的值。数组 $[3, 2, 2]$ 和 $[3, 3, 2]$ 是有效的数组，它们会在懒惰排序结束时让 FJ 高兴。

测试点限制

• 测试点 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: 无额外限制。