Rook
By Microsoft
Serbia
By Microsoft Serbia
There is a generalized chess board of size (N, N) . A rook should move from square (1, 1) to square (N, N). In every move, exactly one coordinate must increase by 1 or more. There are also M occupied squares on the board, so the rook cannot be placed on any of them and cannot jump over them. Squares (1, 1) and (N, N) are not occupied.
In how many ways can the rook reach the square (N, N)?
The first line contains two positive integers N and M delimited by a space, N ≤ 5000, M ≤ 100000. In each of the next M lines there are two positive integers, xi and yi, (1 ≤ xi, yi ≤ N), coordinates of ith occupied square, i = 1, 2, ..., M.
The output contains number of different rook paths, as described above. If this number is 1 million or greater, you should only output its last 6 digits.
| Input Sample | Output Sample |
|
4 2 3 3 4 1 |
48 |