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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

const int mod = 1000000007;
const int N = 300300;

int n;
int a[N], TS[N];
int pref_subtree[N];
int pref_halftree[3][N];
int halftree[3][N];

int res;
vector<pii> vert;
vector<int> vert_top[3][N];

void init() {
	// tree size
	TS[n] = 1;
	for (int i = n-1; i >= 1; i--) TS[i] = (1LL * TS[i+1] * a[i] + 1) % mod;
	
	// subtree sum
	for (int i = 2; i < n; i++) pref_subtree[i] = (1LL * (a[i]-1) * TS[i+1] % mod + pref_subtree[i-1]) % mod;
	
	// halftree sum
	for (int df = 0; df <= 2; df++) {
		for (int h = 1; h <= n; h++) {
			int h0 = h, df0 = df;
			int lsum = 0;
			int cur = 1LL * (a[h]-df0)/2 * TS[h+1] % mod;
			vert_top[df][h].push_back(lsum-h);
			while ((a[h0]-df0)&1) {
				h0++;
				df0=0;
				lsum++;
				cur = (1LL * a[h0]/2 * TS[h0+1] + cur) % mod;
				vert_top[df][h].push_back(lsum-h);
			}
			halftree[df][h] = cur;
			pref_halftree[df][h+1] = (pref_halftree[df][h] + cur) % mod;
		}
	}
}

void attach_path(int h, int df, int lsum, int ldif, bool add_vert=false) {
	if (add_vert) vert.push_back(make_pair(-lsum, (lsum+ldif)/2));
	res = (1LL * (a[h]-df)/2 * TS[h+1] % mod * ldif % mod + res + mod) % mod;
	while ((a[h]-df)&1) {
		h++;
		lsum += 2;
		df=0;
		vert.push_back(make_pair(-lsum, (lsum+ldif)/2));
		res = (1LL * a[h]/2 * TS[h+1] % mod * ldif % mod + res + mod) % mod;
	}
}

void insert_verts(int df, int h, int ha, int hb, int st = 1) {
	for (int i = st; i < SZ(vert_top[df][h]); i++) {
		vert.emplace_back(-(vert_top[df][h][i]*2+ha+hb), vert_top[df][h][i]+ha);
	}
}

int solve(int ha, int hb, int hc) {
	res = 0;
	vert.clear();
	int L = ha+hb-hc*2, La = ha-hc, Lb = hb-hc;
	int dh = ha-hb;
	for (int h = 1; h < hc; h++) insert_verts(1, h, ha, hb, 0);
	res = (1LL*pref_halftree[1][hc]*dh%mod+mod)%mod;
	insert_verts((ha!=hc)+(hb!=hc), hc, ha, hb);
	res = (1LL*halftree[(ha!=hc)+(hb!=hc)][hc]*dh%mod+mod+res)%mod;
	if (La>1 && Lb>1) res = (1LL * (pref_subtree[min(ha,hb)-1] - pref_subtree[hc]) * dh % mod + mod + res) % mod;
	for (int h = max(hb,hc+1); h < ha; h++) attach_path(h, 1, L, dh-(h-hc)*2);
	for (int h = max(ha,hc+1); h < hb; h++) attach_path(h, 1, L, dh+(h-hc)*2);
	if (ha != hc) attach_path(ha, 0, L, -L);
	if (hb != hc) attach_path(hb, 0, L, L);
	if (L%2==0) vert.push_back(make_pair(-L, L/2));
	
	sort(vert.begin(), vert.end());
	for (int i = 0; i < SZ(vert); i++) {
		//cerr << vert[i].fi << " " << vert[i].se << "\n";
		if (i%2==0) res += vert[i].se;
		else res += vert[i].fi + vert[i].se;
		if (res>=mod) res-=mod;
		if (res<0) res+=mod;
		//cerr << "res = " << res << "\n";
	}
	return res;
}

int main() {
	int q;
	scanf("%d%d", &n, &q);
	FORI(i,n-1) scanf("%d", &a[i]);
	init();
	FOR(i,q) {
		int ha,hb,hc;
		scanf("%d%d%d", &ha, &hb, &hc);
		printf("%d\n", solve(ha,hb,hc));
	}
	return 0;
}