Grid 1.5

View as PDF

Submit solution

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

Problem types

In a grid of size W by H (1 \le W,H \le 10^6), you are to determine the number 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 \le X \le 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 \le x \le W) (1 \le y \le 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

3 4 2
2 2
1 4

Sample Output



There are no comments at the moment.