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
#include <iostream>
#include <vector>

#define M 1'000'000'007

int n, q;
std::vector<int> A, B;
std::vector<int> next_nontrivial, sum_trivial, product_right;

inline int posmod(long long int a, long long int b) {
	return (a % b + b) % b;
}

int rev(int b)
{
	int x = 1, y = 0, r = 0, s = 1, a = M;

	while (b != 0) {
		int c = posmod(a, b);
		int p = a / b;
		a = b;
		b = c;

		int r1 = r, s1 = s;
		r = x - p * r;
		s = y - p * s;
		x = r1;
		y = s1;
	}

	return posmod(y, M);
}

void precalc()
{
	long long int sum = 0;
	long long int prod = 1;
	int last = n;

	for (int i = n-1; i >= 0; --i) {
		next_nontrivial[i] = last;
		sum += A[i];
		prod *= B[i];
		prod = posmod(prod, M);
		product_right[i] = prod;
		if (B[i] != 1) {
			last = i;
			sum = 0;
		}
	}
}

int result(int x, int l, int r)
{
	long long int cur;
	int thr;

	cur = x;
	for (int i = l; i < r; ++i) {
		if (cur >= M) {
			cur *= posmod(product_right[i] * rev(product_right[r]), M);
			return posmod(cur, M);
		}

		if (B[i] == 1) {
			if (next_nontrivial[i] < r) {
				cur += sum_trivial[i];
				i = next_nontrivial[i];
				continue;
			}

			return (cur + sum_trivial[i] - sum_trivial[r]) % M;
		}

		if (A[i] + cur > B[i] * cur)
			cur += A[i];
		else
			cur *= B[i];
	}

	return cur % M;
}

int main()
{
	int a, b, x, l, r;

	std::cin >> n >> q;

	A.resize(n);
	B.resize(n);
	next_nontrivial.resize(n);
	sum_trivial.resize(n);
	product_right.resize(n);

	for (int i = 0; i < n; ++i) {
		std::cin >> A[i] >> B[i];
	}

	precalc();

	for (int i = 0; i < q; ++i) {
		std::cin >> x >> l >> r;
		std::cout << result(x, l, r) << std::endl;
	}

	return 0;
}