Path Counting 2

Problem Description

There is an $n \times n$ grid. Some cells are passable, and $m$ cells are obstacles.

You start at the top-left corner. In each step you may move down or right. Count the number of ways to reach the bottom-right corner.

Since the answer can be huge, output the result modulo $10^9+7$.

Input Format

The first line contains two integers $n, m$.

The next $m$ lines each contain two integers $x_i, y_i$, the coordinates of the $i$-th obstacle.

Output Format

Output one number: the answer.

Sample Input

2 1
2 1

Sample Output

1

Constraints

All data guarantee $1 \le n \le 10^6$, $1 \le m \le 3000$, $1 \le x_i, y_i \le n$.