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)\).
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)\)
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\)
4 4 0