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
98
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=1e9+7;
struct S{
  int x; bool b;
  S(int x=0,bool b=false):x(x),b(b){}
  S operator +(const S &r)const{
    S s(x+r.x,b|r.b);
    if(s.x>=P)s.x-=P,s.b=true;
    return s;
  }
  S operator +=(const S &r){
    return *this=*this+r;
  }
  S operator *(const S &r)const{
    if(!x&&!b||!r.x&&!r.b)return S(0,0);
    ll w=1ll*x*r.x;
    return S(w%P,b|r.b|(w>=P));
  }
  S operator *=(const S &r){
    return *this=*this*r;
  }
};
typedef pair<S,S> lf;
lf e(){return lf(S(1),S(0));}
lf comp(lf f,lf g){
  return lf(f.first*g.first,f.second*g.first+g.second);
}
S getv(lf f,S x){
  return f.first*x+f.second;
}
class segtree{
  private:
    int k,m;
    vector<lf> R;
    void pushup(int u){
      R[u]=comp(R[u<<1],R[u<<1|1]);
    }
  public:
    segtree(vector<lf> a){
      int n=a.size();
      k=__lg(n)+(__builtin_popcount(n)>1);
      R.resize((m=1<<k)<<1,e());
      copy(a.begin(),a.end(),R.begin()+m);
      for(int i=m-1;i;i--)
        pushup(i);
    }
    lf prod(int l,int r){
      lf cl=e(),cr=e(); l+=m,r+=m+1;
      while(l<r){
        if(l&1)cl=comp(cl,R[l++]);
        if(r&1)cr=comp(R[--r],cr);
        l>>=1,r>>=1;
      }
      return comp(cl,cr);
    }
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q; cin>>n>>q;
  vector<pair<int,int> > a(n);
  for(auto &[x,y]:a)cin>>x>>y,swap(x,y);
  vector<lf> f(n);
  for(int i=n-1;~i;i--){
    if(a[i].first>1)f[i]=lf(S(a[i].first),S(0));
    else f[i]=lf(S(1),S(a[i].second));
  }
  segtree t(f);
  vector<ll> s(n);
  for(int i=0;i<n;i++)
    s[i]=(i?s[i-1]:0)+a[i].second;
  vector<int> nx(n+1,n),nxa(n+1,n);
  for(int i=n-1;~i;i--){
    nx[i]=a[i].first>1?i:nx[i+1];
    nxa[i]=a[i].second?i:nxa[i+1];
  }
  while(q--){
    int x,l,r; cin>>x>>l>>r,r--;
    int p=x?l:nxa[l]; S v(x);
    while(p<=r){
      if(nx[p]>r||v.b){
        v=getv(t.prod(p,r),v); break;
      }
      if(p<nx[p]){
        ll d=s[nx[p]-1]-(p?s[p-1]:0);
        v+=d>=P?S(d%P,true):S(d),p=nx[p];
      }
      if(v.b)continue;
      if(1ll*v.x*a[p].first>(ll)v.x+a[p].second)v*=S(a[p].first);
      else v+=S(a[p].second);
      p++;
    }
    cout<<v.x<<'\n';
  }
  return 0;
}