In a grid of size by , you are to determine the number of paths from the square to the square that do not go through blocked off squares only moving to the right or up. .
The first line will contain three integers, , , and .
The next lines will contain two integers and .
On one line, you are to output the number of valid paths through the grid modulo .
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
3 4 2 2 2 1 4