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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

const int MAX_N = 500000;
const int MAX_Q = 100000;
const int MAX_D = 20;
const int MODULO = 1000000007;

int A[MAX_N], B[MAX_N], A2[1+MAX_N]; 
int P[MAX_N], Z[MAX_N];

// During Phase 2, going through events i..(i + 2**d-1) transforms x -> (G[i][d]*x + H[i][d]) % MODULO
int G[MAX_N][MAX_D], H[MAX_N][MAX_D];

int res, N, Q, x, l, r;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> Q;
	REP(i, N) {
		cin >> A[i] >> B[i];
		if (i == 0) continue;
	}
	
	// sum(A[i..j]) = A2[j+1] - A2[i]; 
	A2[0] = 0; REP(i, N) {
		long long a2 = A2[i];
		a2 += A[i];
		A2[i+1] = a2 % MODULO;
	}
	
	r = N-1; FORD(i, N-1, 0) { if (A[i] > 0) r = i; Z[i] = r;  } 
	r = N-1; FORD(i, N-1, 0) { if (B[i] != 1) r = i; P[i] = r; }
	
	REP(i, N) {
		G[i][0] = B[i];
		H[i][0] = (B[i] == 1) ? A[i] : 0;
	}
	int d2 = 1;
	FOR(d, 1, MAX_D-1) {
		REP(i, N - d2) {
			// compute {G,H}[i][d] based on {G,H}[{i, i+d2}][d-1];
			long long g1 = G[i][d-1], h1 = H[i][d-1];
			long long g2 = G[i+d2][d-1], h2 = H[i+d2][d-1];
			G[i][d] = (g1*g2) % MODULO;
			H[i][d] = (h2 + g2*h1) % MODULO;
		}		
		d2 *= 2;
	}
	
	REP(iQ, Q) {
		cin >> x >> l >> r;
		//cerr << "iQ=" << iQ << " x=" << x << " l=" << l << " r=" << r << endl;
		
		if (x == 0) { l = (Z[l] < r) ? Z[l] : r-1; }
		
		long long x_lb = x, x_mod = x;
		int i = l; while(i < r) {
			int a = A[i], b = B[i];
			if (b == 1) {
				int p = (P[i] < r) ? P[i] : r-1;
				if (p > i + 1) {
					long long a2 = A2[p]; a2 += MODULO; a2 -= A2[i]; a = a2 % MODULO;
					//cerr << "p="<<p << " i=" << i << " a=" << a << endl;
					x_lb += a; x_mod += a; x_mod %= MODULO;
					i = p; 
					if (x_lb > MODULO) { x_lb = MODULO; break; }
					continue;
				}
			}
			
			//cerr << "i=" << i << " a=" << a << " b=" << b << " x_lb=" << x_lb << " x_mod=" << x_mod << endl;
			if (b == 1 || x_lb <= (a / (b-1))) {
				x_lb += a; x_mod += a;
			} else {
				x_lb *= b; x_mod *= b;
			}
			x_mod %= MODULO;
			i++;
			if (x_lb > MODULO) { 
				x_lb = MODULO; break;				
				//x_lb = MODULO+1;
			}
		}
		// Phase 2
		int d2 = 1, d = 0; 
		while (i+2*d2 <= r) { d2 *= 2; d++; }
		if (x_lb == MODULO) while (i < r) {
			
			//cerr << "i=" << i << " d=" << d << " d2=" << d2 << " x=" << x_mod << endl;
			//cerr << "g=" << G[i][d] << " h=" << H[i][d] << endl;
			x_mod *= G[i][d]; // x_mod %= MODULO;
			x_mod += H[i][d]; x_mod %= MODULO;
			i += d2;
			while (i + d2 > r && d > 0) { d--; d2 /= 2; }

			//int a = A[i], b = B[i];
			//if (b == 1) { x_mod += a; } else { x_mod *= b; }			
			//x_mod %= MODULO;
			//i++;
		}
		
		cout << x_mod << endl;
	}

	return 0;
}