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
#include <bits/stdc++.h>

using namespace std;

#define N 301 * 1000

int n, q, mod=1e9+7, l;
int t[N];
int pr[N];
int gle[N];
int rep[N];
int odl[N][2];
vector <pair <int, int> > zl[N<<2];
vector <int> v[N];

void xd(int x, int y)
{
	rep[y]=x;
	if(y==n) return;
	for(int i=1; i<=t[y]; ++i)
	{
		++l;
		v[x].push_back(l);
		pr[l]=x;
		gle[l]=y+1;
		xd(l, y+1);
	}
}

void dfs(int x, int y, int pop, int dl)
{
	odl[x][y]=dl;
	for(int i:v[x])
	{
		if(i==pop) continue;
		dfs(i, y, x, dl+1);
	}
	if(pr[x]!=pop) dfs(pr[x], y, x, dl+1);
}

void solve()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	int x=rep[a];
	int y=rep[a];
	int last=0;
	int z=a;
	while(z>c)
	{
		last=y;
		y=pr[y];
		--z;
	}
	while(z<b)
	{
		for(int i:v[y])
		{
			if(i!=last)
			{
				y=i;
				++z;
				break;
			}
		}
	}
	dfs(x, 0, 0, 0);
	dfs(y, 1, 0, 0);
	for(int i=1; i<=l; ++i)
	{
		zl[odl[i][0]+odl[i][1]].push_back({odl[i][0], odl[i][1]});
	}
	int odp=0, mv=0;
	for(int i=n<<2; i; --i)
	{
		for(auto j:zl[i])
		{
			if(mv)
			{
				odp-=j.second;
				if(odp<0) odp+=mod;
			}
			else
			{
				odp+=j.first;
				if(odp>=mod) odp-=mod;
			}
			mv^=1;
		}
		zl[i].clear();
	}
	printf("%d\n", odp);
}

int main()
{
	scanf("%d%d", &n, &q);
	for(int i=1; i<n; ++i)
	{
		scanf("%d", &t[i]);
	}
	l=1;
	gle[1]=1;
	xd(1, 1);
	while(q--)
	{
		solve();
	}
	return 0;
}