Submit solution

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

Problem types

Given an 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 \le N \le 1000.

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

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

The next Q lines will each contain a single coordinate point (x_1, x_2, \dots, x_N), 1 \le x_i \le 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.