STAIRCSE - Number of Paths
Jaggi and Jojo are interested in problems related with Grids. They were trying different problem on grids, when they found this one. Given a grid of size N×N. Its bottom-left point is (0, 0) and top-right element is (N-1, N-1).
We can traverse the grid in either top or right direction. You have to find the number of ways to traverse from the bottom-left to top-right point. There are some checkpoints which you have to visit in every path. There is at least one valid path.
Input
The input file consists of several cases T (1 <= T <= 5).
The first line of each case contains a positive integer N (1 <= N <= 1000) specifying the size of grid and the number of checkpoints Q (0 <= Q <= 100).
In next line there are Q space separated coordinates (a, b) of the checkpoints. Checkpoints are 0-Indexed.
Output
For every test case, you have to print the answer modulo 1000000007.
Example
Input: 2 3 0 5 1 2 2 Output: 6 36
Added by: | Rajesh Kumar |
Date: | 2014-11-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |