Count Paths on a Chessboard with Obstacles

You are given an n x n chessboard and a list of obstacles. Each obstacle is represented as a pair of coordinates (row, column) (1-indexed). Your task is to determine the number of distinct paths from the top-left corner (1, 1) to the bottom-right corner (n, n).

You can only move either down or right at any point in time. If either the starting or the ending cell is blocked by an obstacle, the answer is 0.

The answer should be computed using dynamic programming. The recursive formula for the number of ways to reach a cell (i, j) is:

$$dp[i][j] = \begin{cases} 0 & \text{if cell }(i,j) \text{ is an obstacle}, \\ \text{(if not an obstacle)}\; (dp[i-1][j] + dp[i][j-1]) & \text{otherwise}. \end{cases}$$

Note that the indexing for the input obstacles is 1-indexed.

inputFormat

The input is given via stdin and has the following format:

• The first line contains a single integer n, the size of the chessboard.
• The second line contains a single integer k, the number of obstacles.
• The next k lines each contain two integers representing the row and column of an obstacle.

For example:

3
1
2 2

outputFormat

Output a single integer via stdout – the number of distinct paths from cell (1,1) to cell (n,n) under the given constraints.

## sample

3
0

6

</p>