Grid Paths


Submit solution

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

Author:
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\).

Subtasks

Subtask 1 [20%]

\(X = 0\)

Subtask 2 [30%]

\(X = 1\)

Subtask 3 [50%]

\(X = 2\)

Sample Input

4 4 0

Sample Output

20

Comments