Moving through matrix - MarisaOJ: Marisa Online Judge

Moving through matrix

Time limit: 1000 ms
Memory limit: 256 MB
You are given a matrix with $n$ rows and $m$ columns. Currently, you are at position $(1, 1)$, and your goal is to move to position $(n, m)$. However, there are $k$ obstacles, meaning you cannot move to the cells occupied by these obstacles. Count the number of ways to move from cell $(1, 1)$ to $(n, m)$. ### Input - The first line contains three integers $n$, $m$, and $k$. - The next $k$ lines each contain two integers $x$ and $y$, representing the position of an obstacle at row $x$, column $y$. ### Output - Output the number of ways to move, modulo $10^9+7$. ### Constraints - $1 \le n , m \le 10^5$. - $1 \le k \le 100$. - $1 \le x \le n$. - $1 \le y \le m$. ### Example Input: ``` 2 2 1 1 2 ``` Output: ``` 1 ```