Moving through matrix - MarisaOJ: Marisa Online Judge

You are given a matrix with

n

$n$ rows and

m

$m$ columns. Currently, you are at position

(1, 1)

$(1, 1)$ , and your goal is to move to position

(n, m)

$(n, m)$ . However, there are

k

$k$ obstacles, meaning you cannot move to the cells occupied by these obstacles. Count the number of ways to move from cell

(1, 1)

$(1, 1)$ to

(n, m)

$(n, m)$ . Every move, you can choose to move from

(i, j)

$(i,j)$ to either

(i + 1, j)

$(i + 1, j)$ or

(i, j + 1)

$(i, j + 1)$ . ### Input - The first line contains three integers

n

$n$ ,

m

$m$ , and

k

$k$ . - The next

k

$k$ lines each contain two integers

x

$x$ and

y

$y$ , representing the position of an obstacle at row

x

$x$ , column

y

$y$ . ### Output - Output the number of ways to move, modulo

10^{9} + 7

$10^9+7$ . ### Constraints -

1 \leq n, m \leq 10^{5}

$1 \le n , m \le 10^5$ . -

1 \leq k \leq 100

$1 \le k \le 100$ . -

1 \leq x \leq n

$1 \le x \le n$ . -

1 \leq y \leq m

$1 \le y \le m$ . ### Example Input:

22112

$2 2 1 1 2$

Output:

1

$1$

Topic

Math

Combinatorics

Rating

1700

Solution (0)

Solution