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
#include <cstdio>

using namespace std;

#define MAX 524288
//#define MAX 16
//#define MAX 4
#define N 1000000007

typedef long long I;

struct  P{
    I a,b;
};

P buf[MAX*2];

inline I modN(I x) {
    if (x >= N) return (x%N) +N;
    return x;
}

I oblicz(int i,int j, int idx, int l, int r, I x) {
    //printf("[%d,%d) %d [%d,%d) %lld\n", i,j,idx,l,r,x);
    if(j <=l || r<=i) return x;
    if(j-i == 1) {
        if (x* buf[idx].b >= x + buf[idx].a) return modN(x * buf[idx].b);
        else return modN(x+buf[idx].a);
    }
    if(l<=i && j<=r) {
        if (x >= N || buf[idx].b == 1) return modN(x * buf[idx].b + buf[idx].a);
    }
    int ij2 = (i+j)/2;
    I xx =  oblicz(i, ij2, 2*idx,   l, r, x);
    I xx2 = oblicz(ij2, j, 2*idx+1, l, r, xx);
    return xx2;
}

int main() {
    int n,q,a,b;
    scanf("%d %d", &n ,&q);
    for(int i=0;i<n;i++) {
        scanf("%d %d", &a,&b);
        buf[MAX+i] = P{a, b};
    }
    for(int i=n;i<MAX;i++) buf[MAX+i] = P{0,1};
    for(int i=MAX-1;i>0;i--) {
        P l = buf[2*i];
        P p = buf[2*i+1];
        if (i*2 >= MAX) {
            if(l.b > 1) l.a=0;
            if(p.b > 1) p.a=0;
        }
        buf[i] = P{modN(l.a*p.b+p.a), modN(l.b*p.b)};
    }
    for(int i=0;i<q;i++) {
        int x ,l ,r;
        scanf("%d %d %d", &x,&l,&r);
        printf("%lld\n", (oblicz(0, MAX, 1, l, r, x)%N));
    }
}