Submit solution

Points:
20

Time limit:
5.0s

Memory limit:
64M

Author:

Problem types

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given a dimensional grid with coordinates in the form , determine the number of shortest paths from to , that do not pass through blocked points.

A path consists of a series of movements where for any single movement, you must increase a single by unit.

#### Input Specification

The first line will contain a single integer, , .

The next line will contain integers representing , .

The next line will contain a single integer, , .

The next lines will each contain a single coordinate point , .

The points will be unique and will not include or .

#### Output Specification

The number of ways to traverse the grid, modulo .

#### Sample Input

```
2
3 4
2
2 2
1 4
```

#### Sample Output

`3`

## Comments