1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10, mod = 1e9 + 7;
int n, q;
vi V[nax];
int A[nax];
int dep[nax], p[nax], ex[nax], d[nax];
bool visited[nax];
int last = 1;

void create() {
	int x = last;
	ex[dep[x]] = x;
	if(dep[x] == n) return;
	for(int i = 1; i <= A[dep[x]]; ++i) {
		dep[++last] = dep[x] + 1;
		p[last] = x;
		V[last].PB(x);
		V[x].PB(last);
		create();
	}
}

int D, niemoge;

int find_sec(int x) {
	if(dep[x] == D) return x;
	for(int nbh : V[x]) if(nbh != p[x] && nbh != niemoge) {
		return find_sec(nbh);
	}
}

int all;
	
void dfs(int x, int dis) {
	visited[x] = 1;
	d[x] += dis;
	all = (all + dis) % mod;
	for(int nbh : V[x]) if(!visited[nbh]) {
		dfs(nbh, dis+1);
	}
}

int main() {_
	cin >> n >> q;
	for(int i = 1; i < n; ++i) {
		cin >> A[i];
	}
	dep[1] = 1;
	create();
	while(q--) {
		int a, b, c;
		cin >> a >> b >> c;
		int x = ex[a];
		int y = x, block = -1;
		while(dep[y] != c) {
			block = y;
			y = p[y];
		}
		D = b;
		niemoge = block;
		y = find_sec(y);
		for(int i = 1; i <= last; ++i) {
			visited[i] = 0;
			d[i] = 0;
		}
		dfs(x, 0);
		for(int i = 1; i <= last; ++i) {
			visited[i] = 0;
		}
		all = 0;
		dfs(y, 0);
		sort(d + 1, d + last + 1);
		int ans = 0;
		for(int i = last; i >= 1; --i) {
			if((last - i) %2 ==0) {
				ans = (ans + d[i]) % mod;
			}
		}
		ans = (ans - all) % mod;
		if(ans < 0) ans += mod;
		cout << ans << "\n";
	}
	
		
	
}