Paths in a Grid with Obstacles

You are given an N × N grid. You start at the top left corner (1, 1) and your goal is to reach the bottom right corner (N, N). You may only move either right or down at each step.

However, the problem has been made more challenging by placing M obstacles on the grid. You will be given the positions of these obstacles, and you cannot step on a cell that contains an obstacle.

Your task is to calculate the number of paths from (1, 1) to (N, N) without passing through any obstacles.

The movement rule can be defined as follows: in each move, you can go from cell \((i,j)\) either to cell \((i+1,j)\) (down) or to cell \((i,j+1)\) (right). The obstacles are given as coordinates \((r, c)\), where 1 \(\le r, c \le N\).

If the starting cell or the destination cell is blocked by an obstacle, there is no valid path.

inputFormat

The first line contains two integers N and M, where N is the size of the grid and M is the number of obstacles.

Each of the following M lines contains two integers r and c indicating that the cell at row r and column c is blocked.

It is guaranteed that 1 \(\leq N \leq 1000\) and 0 \(\leq M \leq N^2\). The cells are 1-indexed.

outputFormat

Print the number of valid paths from (1, 1) to (N, N) that do not pass through any obstacles.

sample

3 0

6