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

2
3 4
2
2 2
1 4

Sample Output

3