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 <iostream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <cstring>

#define REP(a,n) for (int a = 0; a<(n); ++a)
#define FOR(a,b,c) for (int a = (b); a<=(c); ++a)
#define FORD(a,b,c) for (int a = (b); a>=(c); --a)
#define FOREACH(a,v) for (auto a : v)

#define MP make_pair
#define PB push_back

template<class T> inline int size2(const T&t) { return t.size(); }

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long LL;

///////////////////////////////

#define MOD 1'000'000'007

int N, Q;
int stopnie[300000];
int ile1[300000];
LL ile_w_poddrz[300000];
LL ile_nad[300000];
int parz;

inline void wstaw(int pocz, int ile, vector<bool> &jedynki) {
  //cerr << "wstawiam od " << pocz << " do " << pocz +ile - 1 << endl;
  if (pocz + ile > size2(jedynki))
    jedynki.resize(pocz + ile);
  FOR(a, pocz, pocz + ile - 1)
    jedynki[a] = !jedynki[a];
}
#define wst(a,b) wstaw(a,b,jedynki)

void solveQ() {
  int A, B, LCA;
  cin >> A >> B >> LCA;
  --A;
  --B;
  --LCA;
  vector<bool> jedynki;
  wst(0, LCA + 1);
  FORD(a, LCA - 1, 0)
    if (stopnie[a] % 2 == 0)
      wst(LCA - a + 1, 1 + ile1[a + 1]);
  if ((stopnie[LCA] + (LCA == A) + (LCA == B)) % 2)
    wst(1, 1 + ile1[LCA + 1]);
  if (LCA != A)
    wst(0, 1 + ile1[A]);
  if (LCA != B)
    wst(0, 1 + ile1[B]);
  int start = max(min(A, B), LCA + 1);
  FOR(a, start, max(A, B) - 1)
    if (stopnie[a] % 2 == 0)
      wst(1, 1 + ile1[a + 1]);
  LL res = 0;
  int mn = 1;
  FORD(x, size2(jedynki) - 1, 0)
    if (jedynki[x]) {
      res = (res + MOD + mn*x) % MOD;
      mn = -mn;
    }
  //cerr << "res0: " << res << endl; 
  LL r2 = 0;
  FOR(x, LCA + 1, A) {
    r2 = (r2 + ile_nad[x] - parz + 2 * MOD - ile_w_poddrz[x]) % (2 * MOD);
    //cerr << "dod: " << ile_nad[x]-parz << "-" << ile_w_poddrz[x] << endl;
  }
  FOR(x, LCA + 1, B) {
    r2 = (r2 + ile_w_poddrz[x] - parz + 2 * MOD - ile_nad[x]) % (2 * MOD);
    //cerr << "dod: " << ile_w_poddrz[x]-parz << "-" << ile_nad[x] << endl;
  }
  if (parz) r2 += 2 * (A + B - 2 * LCA);
  assert(r2%2==0);
  //cerr << "r2: " << r2 << endl; 
  res = (r2/2+res)%MOD;
  cout << res << endl;
}

int main() {
  cin >> N >> Q;
  REP(a, N - 1)
    cin >> stopnie[a];
  parz = ile_w_poddrz[N - 1] = 1;
  FORD(a, N - 2, 0) {
    ile_w_poddrz[a] = (1 + stopnie[a] * (LL)ile_w_poddrz[a + 1]) % (2 * MOD);
    parz = (1 + stopnie[a] * parz) % 2;
    ile1[a] = stopnie[a] % 2 ? 1 + ile1[a + 1] : 0;
  }
  FOR(a, 1, N - 1)
    ile_nad[a] = (1 + ile_nad[a - 1] + (stopnie[a - 1] - 1) * (LL)ile_w_poddrz[a]) % (2 * MOD);
//  REP(a, N) cerr << a << ": " << ile_w_poddrz[a] << ", " << ile_nad[a] << endl;
  REP(a, Q) solveQ();
}