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
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

#define FOR(i,b,e) for(int i = (b); i < (e); i++)
#define TRAV(x,a) for(auto &x: (a))
#define SZ(x) ((int)x.size())
#define PB push_back
#define X first
#define Y second

const int N = 3e5+5;
const int mod = 1e9+7;
const int inv2 = (mod+1)/2;

int sumOdl[N], syny[N], subtree[N], layer[N], dist[N], npPath[N];
int n;
bool ziom[N];

int query(int v, int u, int lca){
    int maks = 0;
    int minCost = v + u - 2*lca;
    int distSum = (dist[v] - dist[u] + mod) % mod;
    int ile = 0;
    FOR(j, 0, 2){
        swap(v, u);
        if(v == lca){
            ile++;
            continue;
        }
        FOR(i, 0, npPath[v]) ziom[i] ^= 1;
        maks = max(maks, npPath[v]);
        v--;
        while(v != lca){
            if((syny[v]&1) == 0){
                FOR(i, 1, npPath[v+1]+1) ziom[i] ^= 1;
                maks = max(maks, npPath[v+1]+1);
            }
            ziom[0] ^= 1;
            v--;
        }
    }
    int akt = 0;
    if(ile == 1) akt--, v++;
    else{
        FOR(i, 0, npPath[v]) ziom[i] ^= 1;
        maks = max(maks, npPath[v]);
    }
    v--;
    while(v > 0){
        akt++;
        ziom[akt] ^= 1;
        maks = max(maks, akt);
        if((syny[v]&1) == 0){
            FOR(i, 1, npPath[v+1]+1) ziom[i+akt] ^= 1;
            maks = max(maks, npPath[v+1]+1+akt);
        }
        v--;
    }
    int sign = 1, sum = 0;
    for(int i = maks; i >= 0; i--){
        if(ziom[i]){
            sum = (sum + sign*2*i + mod) % mod;
            sign *= -1;
        }
    }
    if(sign == -1) sum = (sum + minCost) % mod;
    memset(ziom, 0, maks+1);
    return 1ll*(sum + distSum) * inv2 % mod;
}

void solve(){
    int q;
    cin >> n >> q;
    FOR(i, 1, n) cin >> syny[i];
    subtree[n] = 1;
    for(int i = n-1; i > 0; i--) subtree[i] = (1ll*subtree[i+1]*syny[i] + 1) % mod;
    layer[1] = 1;
    FOR(i, 2, n+1) layer[i] = 1ll*layer[i-1]*syny[i-1] % mod;
    FOR(i, 1, n+1) dist[1] = (dist[1] + 1ll*(i-1)*layer[i]) % mod;
    FOR(i, 2, n+1) dist[i] = (dist[i-1] + subtree[1] - 2ll*subtree[i] + 2*mod) % mod;
    for(int i = n; i > 0; i--){
        if(syny[i]&1) npPath[i] = npPath[i+1];
        npPath[i]++;
    }
    FOR(i, 0, q){
        int a, b, c;
        cin >> a >> b >> c;
        cout << query(a, b, c) << '\n';
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    // int tt; cin >> tt;
    // FOR(te, 0, tt)
    solve();
    return 0;
}