时空限制

2S/512M

题目描述

有 $n$ 个修改，第 $i$ 个修改的参数为 $a_i$ 和 $b_i$，对 $x$ 进行第 $i$ 个修改会令 $x=a_i\times x+b_i$。

有 $m$ 个查询，第 $i$ 个查询求对 $x_i$ 依次进行第 $L_i\sim R_i$ 个修改后，对 $10^9+7$ 取模的结果。

格式

输入格式

第一行包含两个整数 $n,m$，分别表示修改的数量和查询的数量。

接下来 $n$ 行每行包含两个整数 $a_i,b_i$，表示第 $i$ 个修改。

接下来 $m$ 行每行包含三个整数 $x_i,L_i,R_i$，表示第 $i$ 个查询。

输出格式

输出 $m$ 行，每行一个整数，第 $i$ 个整数为第 $i$ 个查询的答案。对 $10^9+7$ 取模。

样例

样例输入 #1

3 1
3 1
4 0
2 5
5 1 3

样例输出 #1

133

样例解释 #1

进行第 $1$ 个修改后，$x=3\times 5+1=16$。

进行第 $2$ 个修改后，$x=4\times 16+0=64$。

进行第 $3$ 个修改后，$x=2\times 64+5=133$。

样例输入 #2

5 3
9 7
5 5
101 999
666 12345
233 0
1 1 5
111 3 5
987 1 4

样例输出 #2

490102330
897599758
990987695

数据规模

对于 $10\%$ 的数据，$m\leq 100$。

另有 $20\%$ 的数据，$a_i=0$。

另有 $20\%$ 的数据，$b_i=0$。

对于 $100\%$ 的数据，$1\leq n,m\leq 3\times 10^5$，$0\leq a_i,b_i,x_i\leq 10^9$，$1\leq L_i\leq R_i\leq n$。