Bajtazar bought his girlfriend, Algolina, a huge tree for the holidays. It is an unusual gift, but Bajtazar is an algorithmist, and Algolina has already grown accustomed to such surprises.

As one might guess, the presented tree is not a plant, but a connected graph without cycles. It is very large, but it can be described in an organized way. Its vertices are arranged in $n$ layers. The first layer contains only one vertex – the root of the tree. Each vertex has children only in the next layer, with the exception of vertices in the last layer, which are leaves. For each $i$ in the range $[1, n - 1]$, every vertex in the $i$-th layer has $a_i$ children.

Algolina, wanting to show Bajtazar how much she likes his gift, decided to play a game with him. She chose a certain vertex $A$ in the tree, and Bajtazar chose a vertex $B$ (possibly the same as Algolina). Now, they take turns, starting with Algolina, painting the vertices of the tree – Algolina in red, and Bajtazar in blue. At the beginning of the game, all vertices are white. Each vertex will be painted exactly once – by Algolina or by Bajtazar. At any moment, the player whose turn it is may paint any white vertex with their color, including vertices $A$ and $B$.

When all vertices have been painted, the pair will calculate their scores. Algolina's score (let's denote it $S_A$) will be the sum of distances from all red vertices to vertex $A$, while Bajtazar's score (let's denote it $S_B$) will be the sum of distances from all blue vertices to vertex $B$. By the distance between two vertices, we mean the number of edges on the shortest path between them. Algolina's goal is to obtain the maximum possible advantage over Bajtazar, i.e., to maximize the value $S_A - S_B$, while Bajtazar's goal is to minimize it.

Bajtazar quickly noticed that this is a finite game of perfect information, and assuming both play optimally, the final difference can be calculated. He would like you to help him calculate what it will be. Since it can be very large, it is sufficient to provide the remainder when divided by $10^9 + 7$.

Additionally, since it would be unpleasant to forget the gift after one game, you must calculate the final difference between the scores for many possible variants of choosing vertices $A$ and $B$.

Input

The first line of input contains two integers $n$ and $q$ ($2 \le n \le 300\,000$, $1 \le q \le 300\,000$) denoting the number of layers in the tree and the number of variants for choosing vertices $A$ and $B$, respectively.

The second line contains a sequence of $n - 1$ integers $a_1, a_2, \dots, a_{n-1}$ ($2 \le a_i \le 300\,000$) described in the problem statement.

The next $q$ lines contain descriptions of vertices $A$ and $B$ chosen in successive variants of the game. It can be proven that the final result depends only on which layer vertex $A$ lies in, which layer vertex $B$ lies in, and which layer the lowest common ancestor of vertices $A$ and $B$ lies in. Therefore, the description provides only the numbers of these layers, denoted respectively as $W_A$, $W_B$, and $W_{\text{LCA}(A,B)}$ ($1 \le W_{\text{LCA}(A,B)} \le W_A, W_B \le n$).

Output

The output should contain $q$ lines, where the $i$-th line contains the final difference of scores in the $i$-th game variant, given modulo $10^9 + 7$.

Examples

Input 1

3 3
3 2
3 2 1
1 1 1
2 3 2

Output 1

4
1
1000000003

Note

Explanation of the example: The tree from the test case consists of three layers and contains one vertex in the first layer, three in the second, and six in the third.

In the second game variant, Algolina and Bajtazar both chose the root. In an optimal game, they should choose vertices in order of non-increasing layer numbers, which ends with the result $(2 + 2 + 2 + 1 + 1) - (2 + 2 + 2 + 1 + 0) = 1$.

The third game variant ends with the result $-4$; however, note that in such a case, you should output $-4 \pmod{10^9 + 7} = 10^9 + 3$.

Subtasks

• In some test groups, the tree has at most $300\,000$ vertices and $q \le 100$.
• In other test groups, $q \le 100$.

For each of the above cases, there exists at least one such group.