Lazy Sort

문제

Farmer John has $NN$ cows ($2\le N\le 5\cdot {10}^{6}2\; \backslash leq\; N\; \backslash leq\; 5\backslash cdot\; 10^6$) and is attempting to get them to sort a non-negative integer array $AA$ of length $NN$ by relying on their laziness. He has a lot of heavy boxes so he lines the cows up one behind another, where cow $i+1i+1$ is behind cow $ii$, and gives $a_{i}a\_i$ boxes to cow $ii$ ($0\le a_{i}0\backslash le\; a\_i$).

Cows are inherently lazy so they always look to pass their work off to someone else. From cow $11$ to $N-1N-1$ in order, each cow looks to the cow behind them. If cow $ii$ has strictly more boxes than cow $i+1i+1$, cow $ii$ thinks this is "unfair" and gives one of its boxes to cow $i+1i+1$. This process repeats until every cow is satisfied.

Farmer John will then note the number of boxes $b_{i}b\_i$ that each cow $ii$ is holding and create an array $BB$ out of these values. If $B=sorted(A)B\; =\; sorted(A)$, then Farmer John will be happy. Unfortunately, Farmer John forgot all but $QQ$ values ($2\le Q\le \min (N,100)2\; \backslash leq\; Q\; \backslash leq\; \backslash min(N,\; 100)$) in $AA$. Luckily, those values include the number of boxes he was going to give to the first and last cow. Each value that FJ remembers is given in the form $c_i{v}_{i}c\_i\; v\_i$ representing that $a_{c_i}=v_{i}a\_\{c\_i\}=v\_i$ ($1\le c_i\le N1\; \backslash leq\; c\_i\; \backslash leq\; N$, $1\le v_i\le {10}^{9}1\backslash le\; v\_i\backslash le\; 10^9$). Determine the number of different ways the missing values can be filled in so that he will be happy mod ${10}^9+710^9+7$.

입력

The first line contains two space-separated integers $NN$ and $QQ$ representing the number of cows and queries respectively.

The next $QQ$ lines contain two space separated integers $c_i{v}_{i}c\_i\; v\_i$ representing that cow $c_{i}c\_i$ initially holds $v_{i}v\_i$ boxes. It is guaranteed that $c_1=1c\_1\; =\; 1$, $c_Q=Nc\_Q\; =\; N$, and (the order of the cows is strictly increasing).

출력

Print the number of different ways modulo ${10}^9+710^9+7$ that values $a_{i}a\_i$ can be assigned such that Farmer John will be happy after the cows perform the lazy sort. It is guaranteed that there will be at least one valid assignment.