Submit solution

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

Problem types

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.