A mosquito mesh for a window is in the form of square grid of size $n \times n$. As the mesh is quite old there are $m$ holes in the mesh. A hole of size $l$ in a mesh is a square region of side length $l$ inside which all wires are broken. The centers of the holes lie on the main diagonal of the window.

There is an ant which is at $S (0, 0)$. It has to go to $T (n, n)$. In a single step the ant can go either right or up. i.e. if the ant is at $(x, y)$ it can go to either $(x + 1, y)$ or $(x, y + 1)$, but it is not allowed to go inside any hole or outside of the mesh. Count the number of distinct paths the ant can take to reach $T$ from $S$ .

Since the number of such paths can be very large you have to find the answer modulo $10^9 + 7$

Note: Ant can move on the boundries of both hole or mesh. See the below figure for more clarity.

Constraints:

• $4 \le n \le 10^5$
• $1 \le m \lt n / 2$
• $l_i \ge 2$
• $0 \lt x_i \lt n - 2$
• $x_i + l_i \lt n$
• $x_i + l_i \le x_{i + 1}, \forall 1 \le i \lt m$
• It is guaranteed that no two hole will overlap and no hole share its boundry with window. But two holes can share a corner.

Input Format:

The first line contains two space-separated integers $n$ and $m$  denoting the size of the window and the number of holes respectively.

Next $m$  lines contain two space-separated integer. $i^{th}$ line contains $x_i$ and $l_i$ the x-coordinate of top-left corner of the $i^{th}$ hole and the size of hole respectively. i.e. The top-left corner of the $i^{th}$ hole is at $(x_i, n - x_i)$ and the bottom right corner of the $i^{th}$ hole is at $(x_i + l_i, n - x_i - l_i)$.

Output Format:

Output a single integer denoting the number of distinct paths to reach $T$ from $S$ . Since the output can be very large output the answer modulo $10^9 + 7$