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