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
#include <bits/stdc++.h>

using namespace std;

constexpr uint mod = 1e9 + 7;

vector<size_t> A;
vector<vector<size_t>> graph;

void build(size_t u, size_t i, size_t& curr)
{
    for(size_t c = 0; c < A[i]; c++)
    {
        auto v = curr++;
        graph[u].push_back(v);
        graph[v].push_back(u);
        build(v, i + 1, curr);
    }
}

size_t go(size_t u, size_t k)
{
    if(not k)
        return u;
    for(auto v : graph[u])
        if(u < v)
            return go(v, k - 1);
    __builtin_unreachable();
}

void dists(size_t u, size_t d, vector<uint>& out, size_t lock = SIZE_MAX)
{
    out[u] = d;
    for(auto v : graph[u])
        if(v != lock)
            dists(v, d + 1, out, u);
}


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

    size_t n, q;
    cin >> n >> q;

    size_t m = 1, y = 1;
    A.resize(n);
    for(size_t i = 0; i < n - 1; i++)
        cin >> A[i], m += (y *= A[i]);

    graph.resize(m);
    size_t curr = 1;
    build(0, 0, curr);

    while(q --> 0)
    {
        size_t a, b, c;
        cin >> a >> b >> c; a--; b--; c--;

        auto cv = go(0, c);
        auto av = a > c ? go(graph[cv][(cv!=0)], a - c - 1) : cv;
        auto bv = b > c ? go(graph[cv][(cv!=0) + (av!=cv)], b - c - 1) : cv;

        vector<uint> X(m, UINT_MAX), Y(m, UINT_MAX);
        dists(av, 0, X); dists(bv, 0, Y);
        vector<uint> Z(m);
        for(size_t i = 0; i < m; i++)
            Z[i] = (X[i] + Y[i]) % mod;
        sort(Z.rbegin(), Z.rend());

        uint result = 0;
        for(size_t i = 0; i < m; i += 2)
            result = (result + Z[i]) % mod;
        result = (result + mod) % mod;
        uint sumb = 0;
        for(size_t i = 0; i < m; i++)
            sumb = (sumb + Y[i]) % mod;
        result = (mod + result - (int)sumb) % mod;

        cout << result << '\n';
    }
}