Huge Tree Game

Byteasar bought his girlfriend Algolina a huge Christmas tree. However, this tree is not a plant – it is an acyclic connected graph (i.e. a tree) with a very organized structure. The tree has n levels. The first level contains exactly one vertex (the root). For every level i with 1 ≤ i ≤ n−1, every vertex on level i has exactly a_i children (which all lie on level i+1). The vertices on level n are leaves.

Algolina challenges Byteasar to a game. First, Algolina picks a vertex A and Byteasar picks a vertex B (possibly the same as A). Then, starting with Algolina, they take turns colouring any white (uncoloured) vertex – Algolina uses red and Byteasar uses blue. Every vertex will be coloured exactly once (thus, white at first and then changed to red or blue). At every turn a player may colour any white vertex (including the vertices A and B).

After all vertices have been coloured, the scores are computed. Let \[ S_A = \sum_{x \;\text{red}} d(x,A) \quad\text{and}\quad S_B = \sum_{x\;\text{blue}} d(x,B), \] where \(d(x,y)\) is the number of edges in a shortest path between vertices \(x\) and \(y\). Algolina wants the final difference \(S_A - S_B\) to be as large as possible, while Byteasar wants it to be as small as possible. Since this is a finite complete‐information game, under optimal play the final value of \(S_A - S_B\) is uniquely determined. Byteasar asks you to compute that value modulo \(10^9+7\).

Note on the input: To simplify the problem we assume that, although the tree has a huge number of vertices, its structure is completely described by its levels. In particular, every vertex on a given level has the same distances to any vertex chosen on a fixed level. Hence, in each query the vertices A and B are specified by their level numbers. (In other words, if A is given by an integer, it means that Algolina chooses an arbitrary vertex from level A and similarly for B.)

Game analysis (informal): One may show that under optimal play the effect of the game is equivalent to partitioning the set of vertices (each with a "value" that depends on its distance to A and B) between the two players as follows. For a vertex in level d, define \[ r(d)=|d-A|, \quad b(d)=|d-B|, \quad \text{and} \quad v(d)=r(d)+b(d). \] Then, if we sort all vertices by \(v(d)\) in descending order (if two levels have the same \(v\)-value, a fixed tie–breaking is assumed), the outcome is as if Algolina (red) received all vertices in positions 1, 3, 5, … and Byteasar (blue) got the vertices in positions 2, 4, 6, … . That is, \[ S_A-S_B = \sum_{\substack{\text{positions } i \;\text{odd}}} r(d_i) - \sum_{\substack{\text{positions } j \;\text{even}}} b(d_j), \] where the \(d_i\) are the levels of the vertices when sorted by \(v(d)=|d-A|+|d-B|\). Since the number of vertices on level d is \[ N(d)=\begin{cases} 1, & d=1,\\ \prod_{i=1}^{d-1}a_i, & 2\le d\le n, \end{cases} \] you are asked to compute the final outcome given n, the sequence \(a_1,a_2,\dots,a_{n-1}\) and \(q\) queries (each query consisting of two integers A and B indicating the levels chosen by Algolina and Byteasar, respectively).

Input/Output constraints: Because the total outcome may be huge, output it modulo \(10^9+7\).

inputFormat

The first line contains a single integer n (the number of levels in the tree). The second line contains n−1 space–separated integers: a₁, a₂, …, a_n−1, where for each i (1 ≤ i ≤ n−1) every vertex on level i has exactly a_i children.

The third line contains a single integer q – the number of queries. Each of the next q lines contains two space–separated integers A and B (1 ≤ A, B ≤ n), indicating that Algolina chooses a vertex from level A and Byteasar chooses a vertex from level B.

outputFormat

For each query, output a single line containing the final game outcome \(S_A-S_B\) modulo \(10^9+7\).

sample

2
2
1
1 1

0