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
#include <bits/stdc++.h>
using namespace std;
using ind = long long;
using cind = const ind;
#define FOR(i,l,r) for(ind i = (l); i <= (r); i++)
#define FORD(i,l,r) for(ind i = (l); i >= (r); i--)
#define DEBUG_ON false
#define debug if constexpr(DEBUG_ON)
#define err debug cerr

ind N, Q;

ind A[500'001];
ind B[500'001];
ind sum[500'001];
ind next_mult[500'002];

ind treeA[1 << 21];
ind treeB[1 << 21];

pair<ind,ind> merge(ind A1, ind B1, ind A2, ind B2){
    return {(A1*A2)%1'000'000'007, (B1*A2+B2)%1'000'000'007};
}
void init(ind n, ind l, ind r){
    treeA[n]=1;
    treeB[n]=0;
    if(l == r){
        if(l > N) return;
        if(B[l] != 1) treeA[n] = B[l];
        else treeB[n] = A[l];
    }else{
        init(2*n,l,(l+r)/2);
        init(2*n+1,(l+r+1)/2,r);
        treeA[n] = merge(treeA[2*n], treeB[2*n], treeA[2*n+1], treeB[2*n+1]).first;
        treeB[n] = merge(treeA[2*n], treeB[2*n], treeA[2*n+1], treeB[2*n+1]).second;
    }
}
pair<ind,ind> get_sum(ind n, ind l, ind r, ind nl, ind nr){
    if(r < nl or nr < l) return {1,0};
    if(l <= nl and nr <= r) return {treeA[n], treeB[n]};
    auto p1 = get_sum(2*n,l,r,nl,(nl+nr)/2);
    auto p2 = get_sum(2*n+1,l,r,(nl+nr+1)/2,nr);
    return merge(p1.first, p1.second, p2.first, p2.second);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> Q;
    FOR(i,1,N) cin >> A[i] >> B[i];
    sum[0]=0;
    FOR(i,1,N) sum[i] = sum[i-1] + A[i];
    next_mult[N] = N+1;
    FORD(i,N,2){
        next_mult[i-1] = next_mult[i];
        if(B[i] > 1) next_mult[i-1] = i;
    }
    init(1,1,1<<20);
    FOR(qi,1,Q){
        ind now,l,r;
        cin >> now >> l >> r;
        l++;
        ind i = l;
        while(i <= r){
            if(now + A[i] > now * B[i]) now += A[i];
            else now *= B[i];
            if(next_mult[i] > r){
                now += sum[r]-sum[i];
                i = r+1;
                break;
            }
            now += sum[next_mult[i]-1] - sum[i];
            i = next_mult[i];
            if(now > 1'000'000'007) break;
        }
        now %= 1'000'000'007;
        if(i <= r){
            auto operation = get_sum(1,i,r,1,1<<20);
            now = now*operation.first+operation.second;
        }
        cout << now % 1'000'000'007 << '\n';
    }
}