거대한 나무

바이타자르는 여자친구 알고리나에게 크리스마스 선물로 거대한 나무를 주었다. 이 나무는 식물이 아니라 사이클이 없는 연결 그래프이다. 나무는 매우 크지만 정리된 구조를 가진다.

나무의 정점은 $n$개의 층에 놓여 있다. 첫 번째 층에는 정점이 하나뿐이며, 이것이 뿌리이다. 각 정점은 바로 다음 층에만 자식을 가진다. 마지막 층의 정점들은 잎이다. 모든 $i \in [1, n-1]$에 대해 $i$번째 층의 각 정점은 $a_i$개의 자식을 가진다.

알고리나는 선물이 얼마나 마음에 드는지 보여 주려고 바이타자르와 게임을 하기로 했다. 알고리나는 나무에서 정점 $A$를 골랐고, 바이타자르는 정점 $B$를 골랐다. $B$는 $A$와 같을 수도 있다. 알고리나부터 시작해서 두 사람이 번갈아 정점을 칠한다. 알고리나는 빨간색으로, 바이타자르는 파란색으로 칠한다. 게임을 시작할 때 모든 정점은 흰색이다. 각 정점은 알고리나 또는 바이타자르가 정확히 한 번만 칠한다. 차례인 사람은 흰색 정점이라면 $A$와 $B$를 포함해 아무 정점이나 자기 색으로 칠할 수 있다.

모든 정점이 칠해지면 두 사람은 점수를 계산한다. 알고리나의 점수 $S_A$는 빨간 정점 각각과 $A$ 사이 거리의 합이다. 바이타자르의 점수 $S_B$는 파란 정점 각각과 $B$ 사이 거리의 합이다. 두 정점 사이의 거리는 두 정점을 잇는 가장 짧은 경로의 간선 수이다. 알고리나는 $S_A - S_B$를 최대로 만들고, 바이타자르는 이를 최소로 만들려고 한다.

바이타자르는 이것이 유한한 완전정보 게임이며, 두 사람이 최선을 다하면 최종 차이를 계산할 수 있다는 것을 금방 알아챘다. 값이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지만 구하면 된다.

선물을 한 판만 하고 잊어버리기는 아쉬우니, 가능한 $A$와 $B$의 여러 선택마다 최종 점수 차이를 구해야 한다.

첫 줄에는 정수 $n$과 $q$가 주어진다 ($2 \le n \le 300000$, $1 \le q \le 300000$). 각각 층의 수와 $A$, $B$를 고르는 경우의 수이다.

둘째 줄에는 정수 $a_1, a_2, \ldots, a_{n-1}$이 주어진다 ($2 \le a_i \le 300000$).

이후 $q$개의 줄에는 각 경우가 주어진다. 정점 자체가 아니라 층 번호만 주어지며, $A$가 있는 층 $W_A$, $B$가 있는 층 $W_B$, $A$와 $B$의 최소 공통 조상이 있는 층 $W_{LCA(A,B)}$ 세 값이다 ($1 \le W_{LCA(A,B)} \le W_A, W_B \le n$). 최종 결과는 이 세 값에만 의존한다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 경우의 최종 점수 차이를 $10^9 + 7$로 나눈 값을 쓴다.

이 나무는 3개 층으로 이루어져 있으며, 첫 번째 층에 정점 1개, 두 번째 층에 3개, 세 번째 층에 6개가 있다.

두 번째 경우에는 알고리나와 바이타자르가 모두 뿌리를 골랐다. 최적의 진행에서 두 사람은 층 번호가 커지지 않는 순서로 정점을 고른다. 결과는 $(2+2+2+1+1)-(2+2+2+1+0)=1$이다.

세 번째 경우의 결과는 $-4$이다. 출력해야 하는 값은 $-4 \bmod (10^9+7) = 10^9+3$이다.