Grid 1.5

View as PDF

Points: 10 (partial)
Time limit: 0.4s
Memory limit: 64M

Problem types

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 .

Sample Input

3 4 2
2 2
1 4

Sample Output

3