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
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MOD=1e9+7;
long long a[300010];
long long odl[300010];
long long siz[300010];
long long pref_odl[300010];
long long pref_siz[300010];
long long add_pref_odl[300010];
int nxt[300010];
int rem[600010];
int ev[600010];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q,x,y,lca,i;
	long long b,d;
	cin>>n>>q;
	for(i=1;i<n;i++)
		cin>>a[i];
	odl[n]=0;
	siz[n]=1;
	nxt[n]=n;
	for(i=n-1;i>0;i--)
	{
		nxt[i]=(a[i]%2==0 ? i:nxt[i+1]);
		siz[i]=(a[i]*siz[i+1]+1)%MOD;
		odl[i]=(a[i]*(odl[i+1]+siz[i+1]))%MOD;
	}
	for(i=1;i<=n;i++)
	{
		pref_odl[i]=(pref_odl[i-1]+(a[i]-1)*(odl[i+1]+siz[i+1]))%MOD;
		pref_siz[i]=(pref_siz[i-1]+(a[i]-1)*siz[i+1]+1)%MOD;
		add_pref_odl[i]=(add_pref_odl[i-1]+pref_siz[i])%MOD;
		//cerr<<i<<" "<<odl[i]<<" "<<siz[i]<<" "<<pref_odl[i]<<" "<<pref_siz[i]<<" "<<add_pref_odl[i]<<"\n"; 
	}
	while(q--)
	{
		cin>>x>>y>>lca;
		b=(pref_odl[x-1]+add_pref_odl[x-1]+odl[x])%MOD;
		d=((a[lca]-2)*(odl[lca+1]+siz[lca+1]))%MOD;
		if(x!=lca)
			d=(d+pref_odl[x-1]-pref_odl[lca]+odl[x])%MOD;
		else
			d=(d+odl[lca+1]+siz[lca+1])%MOD;
		if(y!=lca)
			d=(d+pref_odl[y-1]-pref_odl[lca]+odl[y])%MOD;
		else
			d=(d+odl[lca+1]+siz[lca+1])%MOD;
		d=(d+pref_odl[lca-1]+add_pref_odl[lca-1])%MOD;
		d=(2*d+siz[1]*(x+y-2*lca))%MOD;
		//cerr<<b<<" "<<d<<"\n";
		rem[0]=(x+y-2*lca+1)%2;
		if((x!=lca)&&(y!=lca))
		{
			ev[nxt[x]-x+1]++;
			ev[nxt[y]-y+1]++;
			ev[nxt[lca]-lca+1]++;
		}
		else if(x!=lca)
		{
			ev[nxt[x]-x+1]++;
			if(a[lca]%2==1)
				ev[1]++;
			else
				ev[nxt[lca+1]-lca+1]++;
		}
		else if(y!=lca)
		{
			ev[nxt[y]-y+1]++;
			if(a[lca]%2==1)
				ev[1]++;
			else
				ev[nxt[lca+1]-lca+1]++;
		}
		else
			ev[nxt[lca]-lca+1]++;
		for(i=lca+1;i<x;i++)
		{
			if(a[i]%2==1)
				ev[1]++;
			else
				ev[nxt[i+1]-i+1]++;
		}
		for(i=lca+1;i<y;i++)
		{
			if(a[i]%2==1)
				ev[1]++;
			else
				ev[nxt[i+1]-i+1]++;
		}
		for(i=lca-1;i>0;i--)
		{
			ev[lca-i]++;
			if(a[i]%2==1)
				ev[lca-i+1]++;
			else
				ev[lca-i+nxt[i+1]-i+1]++;
		}
		for(i=1;i<=2*n;i++)
		{
			rem[i]=(rem[i-1]+ev[i])%2;
			ev[i]=0;
		}
		long long xd=-1;
		for(i=2*n;i>=0;i--)
		{
			if(rem[i]==1)
			{
				d=(d+xd*(2*i+x+y-2*lca))%MOD;
				xd=-xd;
			}
		}
		d=(d*((MOD+1)/2))%MOD;
		cout<<((b-d)%MOD+MOD)%MOD<<"\n";
	}
	return 0;
}