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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
///////////////////
#define debug if(1)
///////////////////

const int MAXN=3e5+10;
const int mod=1e9+7;
const ll inv=5e8+4;

int nodes=0;
vector<int> g[MAXN];
int a[MAXN];
int cost[MAXN];
int cnt[MAXN*2];
int my_pos[MAXN];

void prep(int id,int pos,int max_pos){
	my_pos[id]=pos;
	if(pos==max_pos)
		return;
	for(int i=0;i<a[pos];i++){
		nodes++;
		g[nodes].eb(id);
		g[id].eb(nodes);
		prep(nodes,pos+1,max_pos);
	}
}

int get(int u,int req_pos,bool lewy){
	if(my_pos[u]==req_pos)
		return u;
	if(lewy)
		return get(g[u][1],req_pos,lewy);
	return get(g[u][size(g[u])-1],req_pos,lewy);
}

int ans;

void dfs(int u,int d,int col,int p=-1){
	if(!col){
		ans+=d;
		if(ans>=mod)
			ans-=mod;
	}
	else{
		ans-=d;
		if(ans<0)
			ans+=mod;
	}
	cost[u]+=d;
	for(auto v:g[u])
		if(v!=p&&v!=0)
			dfs(v,d+1,col,u);
}

int32_t main()
{
	fastio;
	int n,q;
	cin>>n>>q;
	for(int i=1;i<n;i++)
		cin>>a[i];
	g[1].eb(0);
	nodes=1;
	prep(1,1,n);
	int l,r,lca,turn;
	ll ansans;
	while(q--){
		cin>>l>>r>>lca;
		lca=get(1,lca,0);
		l=get(lca,l,0);
		r=get(lca,r,1);
		fill(cost+1,cost+nodes+1,0);
		fill(cnt,cnt+nodes+nodes+1,0);
		ans=0;
		dfs(l,0,0);
		dfs(r,0,1);
		for(int i=1;i<=nodes;i++)
			cnt[cost[i]]++;
		turn=0;
		for(int i=nodes*2;i>=0;i--){
			while(cnt[i]>0){
				if(!turn){
					ans+=i;
					if(ans>=mod)
						ans-=mod;			
				}
				else{
					ans-=i;
					if(ans<0)
						ans+=mod;
				}
				cnt[i]--;
				turn^=1;
			}
		}
		ansans=ans;
		ansans=(ansans*inv)%mod;
		cout<<ansans<<'\n';
	}
		
}