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\)