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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const int Q = ((int)1e9) + 7;

void dod(int &x, long long y) {
  x += y % Q;
	if (x >= Q) x -= Q;
}

struct drz {
	int get(long long r, long long aa = 2) {
	  return (sum * aa + r * num) % Q;
	}

	void fill(vector<int>& v, int r) {
		for (int i = 0; i < g; i++) v.push_back(r+i+i);
	}

	int sum;
	int num;
	int g;
};

drz mnd(const drz& d, long long a) {
  drz ret;
	ret.g = (a % 2 == 0 ? 1 : d.g + 1);
	ret.num = (a * d.num + 1) % Q;
	ret.sum = (a * (d.num + d.sum)) % Q;
	return ret;
}

int div2(int x) {
  x %= Q;
	if (x % 2) x+=Q;
	return x/2;
}

int main() {
  int n,q;
	scanf("%d %d",&n,&q);
	vector<int> a(n-1);
	for (int i = 0; i < n-1; i++) {
		scanf("%d",&a[i]);
	}
	vector<drz> d(n);
	d[n-1].sum = 0;
	d[n-1].num = 1;
	d[n-1].g = 1;
	for (int i = n-2; i >= 0; i--) {
		d[i] = mnd(d[i+1], a[i]);
	}
	for (int ii = 0; ii < q; ii++) {
		int A,B,C,odwr=0;
		scanf("%d %d %d",&A,&B,&C);
		A--,B--,C--;
		if (B > A) swap(A, B), odwr=1;
		int odl = A-C + B-C;
		int oA = 0;
		int ret = d[A].get(odl);
		int sumA = d[A].get(oA, 1);
		vector<int> s;
		d[A].fill(s, odl);
		while (A > B) {
		  A--;
			oA++;
			drz x = mnd(d[A+1], a[A]-1);
			dod(ret, x.get(odl));
			dod(sumA, x.get(oA, 1));
			x.fill(s, odl);
		}
		if (B > C) {
			dod(ret, d[B].get(odl));
			dod(sumA, d[B].get(odl, 1));
			d[B].fill(s, odl);
		}
		int oAB = odl;
		while (A > C) {
			A--, B--;
			oA++;
			oAB--;
			if (A > C) {
				// jednakowe
				drz x = mnd(d[A+1], a[A]-1);
				dod(ret, x.get(odl) * 2);
				dod(sumA, x.get(oA, 1) + x.get(oAB, 1));
			} else {
			  // w C
				drz x = mnd(d[A+1], a[A]-2);
				dod(ret, x.get(odl));
				dod(sumA, x.get(oA, 1));
				x.fill(s, odl);
			}
		}
		while(C > 0) {
			C--;
			odl += 2;
			oA++;
			drz x = mnd(d[C+1], a[C]-1);
			dod(ret, x.get(odl));
			dod(sumA, x.get(oA, 1));
			x.fill(s, odl);
		}
		long long ss = 0, ssB = 0;
		sort(s.begin(), s.end());
		for (int i = 0; i < s.size(); i++) ss += s[i];
		for (int i = s.size()-2; i >= 0; i-=2) ssB += s[i];
		if (odwr) sumA = (ret-sumA+Q)%Q;
	//	printf("sumA = %d\nret = %d\nss = %lld\n,ssB = %lld\n",sumA,ret,ss,ssB);
//		printf("{"); for (int i = 0; i < s.size(); i++) printf(" %d", s[i]); printf("}\n");
		int xx = ((sumA - div2(ret - ss%Q + Q) - ssB % Q) % Q + Q) % Q;
		printf("%d\n", xx);
	}
	return 0;
}