Grid Paths

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