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)~.
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)~
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~
3 4 2 2 2 1 4