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.
.
Input Specification
The first line will contain three integers, ,
, and
.
The next lines will contain two integers
and
.
Output Specification
On one line, you are to output the number of valid paths through the grid modulo .
Subtasks
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
Sample Input
3 4 2
2 2
1 4
Sample Output
3
Comments