高仿的 Migos

经过刻苦的训练，ZHY 终于成为了一名说唱歌手。但这天，说唱歌手 ZHY 看到了同行说唱组合 Migos 的作品，立刻意识到了自己的差距，于是他要学习 Migos 的说唱技巧，复刻 Migos 的成功。 经过数个日夜的研究，ZHY 最终挑选出了 $n$ 部 Migos 的说唱作品，依次编号为 $1,2,\dots,n$。他认为只要学习完这 $n$ 部作品，就可以成为更加优秀的说唱歌手。于是，他会从第 $1$ 部作品，按编号从小到大的顺序依次进行学习，学习完第 $n$ 部作品就结束学习。 不过，说唱歌手 ZHY 的学习方式很特殊。对于每部作品，他只会听 $1$ 分钟。这种学习方式的问题是，对于第 $i$ 部作品，他在投入 $1$ 分钟后，有可能学习成功，也有可能会失败，具体地，如果 ZHY 学习的是作品 $i$，那么在他花一分钟的时间进行学习后： - 有 $P_i$ 的概率，ZHY 学习成功了，那么他会接着去学习作品 $i+1$（当然如果 $i=n$ 就直接结束学习）。 - 有 $1-P_i$ 的概率，ZHY 学习失败了。不幸的是，ZHY 脑内的记忆还会因此产生混乱，导致他只会记住前 $x_i$ 部作品，即他必须从第 $x_i+1$ 部作品开始重新学习。 ZHY 在尝试了几次学习后，深受记忆混乱的困扰，于是向脑科学专家 YHZ 求助。经过脑科学专家 YHZ 的研究，他发现所有的 $x_i$ 有一定的规律。具体地，他发现有 $m$ 对自然数 $(l_i,r_i)$, 其中 $i=1,2\dots,m$，满足 $0\leq l_i<r_i\leq n$，那么 $x_i=\max\limits_{j=1}^m\{l_j \mid l_j+1\leq i\leq r_j\}$，特别地，如果对于所有 $1\leq j\leq m$，都**不满足** $l_j+1\leq i\leq r_j$，那么 $x_i=0$。 现在，ZHY 对自己的学习能力有了充分了解，但刚才的尝试让他疲惫不堪，所以他决定休息 $1$ 秒，并希望你帮他计算一下他期望多少分钟可以结束学习。不过他意识到，自己如果每部作品只学固定的 $1$ 分钟是不够全面的，所以他决定更改一些作品他所会学习的那一分钟，这会导致他学习这一部作品的成功概率发生改变。具体地，现在 ZHY 提出了 $k$ 个要求，每个要求有两种可能： 1. 修改某个作品 $i$ 学习成功的概率 $P_i$。 1. 询问以当前的概率他学习完 $n$ 部作品期望要多少分钟。 由于 ZHY 要休息，所以他找上了你，希望你来解决他的要求。对于他的每个第二种要求，你要告诉他期望时间对 $10^9+7$ 取模的结果。ZHY 给了你 $1$ 秒的时间，因为他只能休息这么久。

第一行三个整数 $n,m,k$。意思如题面所述。 接下来 $n$ 行，每行两个正整数 $p_i,q_i$，表示 $P_i=\frac{p_i}{q_i}$。 接下来 $m$ 行，每行两个整数 $l_{i},r_{i}$。 接下来 $k$ 行，每行都是以下两种格式的其中一种： - `1 x a b` 为修改操作。表示 $P_x$ 变成了 $\frac a b$。保证 $1\le x \le n$，$1 \le a \le b < 10^9+7$ 且 $x,a,b$ 均为正整数。 - `2` 为查询操作。表示询问此时结束学习的期望时间是多少。对 $10^9+7$ 取模。

对于每个询问，输出一行一个整数表示答案。

3 1 3
1 3
2 3
1 4
2 3
2
1 2 4 5
2

10
9

2 1 1
1 1
1 2
0 2
2

4

2 1 1
1 1
1 2
1 2
2

3

**本题使用捆绑测试。** | Subtask 编号 | $n$ | $m$ | $k$ | 特殊性质 |分值 | | :-----: | :-----: | :-----: | :-----: | :-----: | :-----: | | $0$ | $\le 300$ | $\le 300$ | $\le 300$ | 无 | $11$ | | $1$ | $\le 3000$ | $\le 3000$ | $\le 3000$ | 无 | $4$ | | $2$ | $\le 10^5$ | $\le 10^5$ | $\le 1$ | B | $5$ | | $3$ | $\le 10^5$ | $\le 10^5$ | $\le 1$ | 无 | $14$ | | $4$ | $\le 10^5$ | $=0$ | $\le 10^5$ | 无 | $19$ | | $5$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | A | $19$ | | $6$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | B | $8$ | | $7$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | C | $10$ | | $8$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 无 | $10$ | 以下的“区间”均指 $[l_i,r_i]$。 特殊性质 A：保证对于 $\forall i \in [1,m]$，$r_i-l_i+1\le 5$。 特殊性质 B：保证这些区间两两的交 $\le 1$。即对于 $\forall i,j \in [1,m]$ 且 $i\ne j$，有 $r_i\le l_j$ 或 $r_j\le l_i$。 特殊性质 C：保证这些区间不存在包含关系。即对于 $\forall i,j \in [1,m]$ 且 $i\ne j$，有 $l_i>l_j$ 或 $r_i<r_j$。 对于 $100\%$ 的数据，$1 \le n,k \le 10^5$，$0 \le m \le 10^5$，$1 \le p_{i} \le q_{i} \lt 10^{9}+7$，$0 \le l_{i} \lt r_{i} \le n$。