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