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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < ll, ll > pii;
const ll lim = 1000'003, mod = 1e9 + 7;

ll tab[lim][2];
ll pt[lim];
ll pref[lim][2];
ll suma[lim];

ll zmod(ll x){
    x %= mod;
    if(x < 0) x+= mod;
    return x;
}

ll fast_pow(ll base, ll x){
    ll ans = 1;
    while (x > 0){
        if(x % 2 == 1) ans *= base;
        base *= base;
        x /= 2;
        base = zmod(base);
        ans = zmod(ans);
    }
    return ans;
}

ll dec(ll x, int i){
    if(((tab[i][1] - 1) * x) >= tab[i][0]) return x * tab[i][1];
    else return x + tab[i][0];
}

ll sum(int l, int r){
    if(l > r) return 0;
    return zmod(pref[r][0] - pref[l - 1][0]);
}

pii przemnoz(int l, int r){
    ll odwr = fast_pow(pref[l - 1][1], mod - 2);
    ll iloczyn = zmod(pref[r][1] * odwr);
    return {iloczyn, zmod(suma[r] - zmod(suma[l - 1] * iloczyn))};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, q;
    cin >> n >> q;
    pref[0][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 2; j++) {
            cin >> tab[i][j];
        }
        pref[i][0] = pref[i - 1][0] + tab[i][0];
        pref[i][1] = pref[i - 1][1] * tab[i][1];
        suma[i] = suma[i - 1] * tab[i][1];
        if(tab[i][1] == 1) suma[i] += tab[i][0];
        suma[i] = zmod(suma[i]);
        for(int j = 0; j < 2; j++) pref[i][j] = zmod(pref[i][j]);
    }
    int nast = n + 1;
    for(int i = n; i >= 1; i--){
        pt[i] = nast;
        if(tab[i][1] > 1) nast = i;
    }

    for(int i = 0; i < q; i++){
        ll x, a, b;
        cin >> x >> a >> b;
        a++;
        x = dec(x, a);
        
        while (x < mod && pt[a] <= b){
            x += sum(a + 1, pt[a] - 1);
            a = pt[a];
            x = dec(x, a);
        }
        if(x < mod){ //przerwane bo pt[a] > b
            x += sum(a + 1, b);
            x = zmod(x);
        }
        else {
            x = zmod(x);
            pii z = przemnoz(a + 1, b);
            x *= z.first;
            x += z.second;
            x = zmod(x);
        }
        
        cout << x << "\n";
    }
}