题目描述

众所周知，一次函数可以表示为如下形式：$f(x) = kx + b$。

现有 $n$ 个一次函数 $f_i(x)=k_ix+b_i$，需要对这 $n$ 个一次函数执行 $m$ 次操作，每次操作为下列格式之一：

1. M i K B：代表把第 $i$ 个线性函数改为：$f_i(x)=Kx+B$。
2. Q l r x：求 $f_r(f_{r-1}(...f_l(x)))$ 的值，并对 $10^9+7$ 取模。

输入格式

第一行两个整数 $n, m$。

接下来 $n$ 行，每行两个整数 $k_i, b_i$。

接着是 $m$ 行询问或修改，每行的格式为 M i K B 或者 Q l r x。

输出格式

对于每个 Q 操作，输出一行答案（对 $10^9+7$ 取模）。

5 5
4 2
3 6
5 7
2 6
7 5
Q 1 5 1
Q 3 3 2
M 3 10 6
Q 1 4 3
Q 3 4 4

1825
17
978
98

数据范围

$1 \le n, m \le 2 \times 10^5$

$1 \le l \le r \le n$

$0 \le k_i, b_i, x < 10^9+7$

题目来源：BZOJ4499.