Submit solution

Points: 20
Time limit: 5.0s
Memory limit: 64M

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 N dimensional grid with coordinates in the form (x_1, x_2, \dots, x_N), determine the number of shortest paths from (1, 1, \dots, 1) to (a_1, a_2, \dots, a_N), that do not pass through Q blocked points.

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

Input Specification

The first line will contain a single integer, N, 1 \leq N \leq 1000.

The next line will contain N integers representing (a_1, a_2, \dots, a_N), 1 \leq a_i \leq 1000.

The next line will contain a single integer, Q, 0 \leq Q \leq 1000.

The next Q lines will each contain a single coordinate point (x_1, x_2, \dots, x_N), 1 \leq x_i \leq a_i.

The Q points will be unique and will not include (a_1, a_2, \dots, a_N) or (1, 1, \dots, 1).

Output Specification

The number of ways to traverse the grid, modulo 10^9 + 7.

Sample Input

3 4
2 2
1 4

Sample Output



There are no comments at the moment.