Grid Paths

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

In a grid of size W by H (1 \leq W,H \leq 10^6), you are to determine the amount of paths from the square (1,1) to the square (W,H) that do not go through X blocked off squares only moving to the right or up. (0 \leq X \leq 2).

Input Specification

The first line will contain three integers, W, H, and X.

The next X lines will contain two integers x and y. (1 \leq x \leq W) (1 \leq y \leq H)

Output Specification

On one line, you are to output the number of valid paths through the grid modulo 10^9 + 7.


Subtask 1 [20%]

X = 0

Subtask 2 [30%]

X = 1

Subtask 3 [50%]

X = 2

Sample Input

4 4 0

Sample Output