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
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod=1e9+7, N=5e5+5;
int deg[N], siz[N], siz2[N], val[N], ter[N];
int div(ll a){
    if(a&1)a+=mod;
    return (a/2)%mod;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, q;
    cin>>n>>q;
    for(int i=1; i<n; i++){
        cin>>deg[i];
    }
    deg[n]=0;
    siz[n]=1;
    ter[n]=1;
    for(int i=n-1; i>0; i--){
        ter[i]=ter[i+1]+1;
        if(!(deg[i]&1))ter[i]=1;
        siz[i]=(1+siz[i+1]*1ll*deg[i])%mod;
    }
    int cnt=1;
    for(int i=1; i<=n; i++){
        val[1]=(val[1]+(i-1)*1ll*cnt)%mod;
        cnt=(cnt*1ll*deg[i])%mod;
    }
    for(int i=2; i<=n; i++){
        val[i]=((val[i-1]+siz[1]-2*siz[i])%mod+mod)%mod;
    }
    //cout<<ter[1]<<" ;";
    vector<int> V(2*n);
    while(q--){
        int a, b, m;
        cin>>a>>b>>m;
        for(int i=a; i>m; i--){
            V[0]^=1;
            V[ter[i]]^=1;
        }
        for(int i=b; i>m; i--){
            V[0]^=1;
            V[ter[i]]^=1;
        }
        //V[0]^=1;
        for(int i=m; i>1; i--){
            V[m-i]^=1;
            V[m-i+1]^=1;
            V[m-i+ter[i]]^=1;
            V[m-i+ter[i]+1]^=1;
        }
        for(int i=0; i<ter[1]; i++){
            V[i+m-1]^=1;
        }
        int d=0;
        bool B=1;
        for(int i=2*n-1; i>=0; i--){
            if(V[i]){
                //cout<<i<<" ";
                if(B)d+=i;
                else d-=i;
                B=1-B;
                V[i]=0;
                d=(d+mod)%mod;
            }
        }
        d*=2;
        if(B==0){
            d+=a+b-m-m;
        }
        //cout<<val[a]<<" "<<val[b]<<" "<<d<<"\n";
        cout<<((val[a]-div(val[a]+val[b]-d))%mod+mod)%mod<<"\n";
    }
}