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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

struct Layer{
    ll distA, distB;
    ll size;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,q;
    cin >> n >> q;

    vector<ll>A(n);
    for(int i=1;i<n;i++)
        cin >> A[i];
    
    while(q--){
        int Wa,Wb,Wlca;
        cin >> Wa >> Wb >> Wlca;
        vector<Layer>L;

        auto build_layers = [&](ll distA, ll distB, int rootLayer, bool addRoot, int firstSkip){
            ll size = 1;

            if(addRoot)
                L.push_back(Layer{distA, distB, size});

            for(int l=rootLayer;l<n;l++){
                size = (size*(A[l]-firstSkip))%MOD;
                distA++;
                distB++;
                firstSkip = 0;

                L.push_back(Layer{distA, distB, size});
            }
        };

        //build layers above LCA
        for(int layer=Wlca-1;layer>0;layer--)
            build_layers(Wa-layer, Wb-layer, layer, true, 1);

        //build layers from LCA
        if(Wa!=Wlca && Wb!=Wlca)
            build_layers(Wa-Wlca, Wb-Wlca, Wlca, true, 2);
        else if(Wa!=Wlca || Wb!=Wlca)
            build_layers(Wa-Wlca, Wb-Wlca, Wlca, true, 1);
        else
            build_layers(0, 0, Wlca, true, 0);
        
        //build layers between
        for(int l=Wlca+1;l<Wa;l++)
            build_layers(Wa-l, l+Wb-2*Wlca, l, true, 1);
        for(int l=Wlca+1;l<Wb;l++)
            build_layers(l+Wa-2*Wlca, Wb-l, l, true, 1);

        //build layers from A,B
        if(Wa!=Wlca)
            build_layers(0, Wa+Wb-2*Wlca, Wa, true, 0);
        if(Wb!=Wlca)
            build_layers(Wa+Wb-2*Wlca, 0, Wb, true, 0);

        //process layers
        sort(L.begin(), L.end(), [](const Layer& l1, const Layer& l2){
            return l1.distA+l1.distB > l2.distA+l2.distB;
        });

        ll result = 0;
        bool half=false;
        for(Layer l : L){
            if(half){
                result += l.distA*(l.size/2);
                result -= l.distB*((l.size+1)/2);
                if(l.size%2==1)
                    half=false;
            }
            else{
                result += l.distA*((l.size+1)/2);
                result -= l.distB*(l.size/2);
                if(l.size%2==1)
                    half=true;
            }

            result %= MOD;
        }
        
        cout << (result+MOD)%MOD << "\n";
    }

    return 0;
}