{"problem":{"name":"高仿的 Migos","description":{"content":"经过刻苦的训练，ZHY 终于成为了一名说唱歌手。但这天，说唱歌手 ZHY 看到了同行说唱组合 Migos 的作品，立刻意识到了自己的差距，于是他要学习 Migos 的说唱技巧，复刻 Migos 的成功。 经过数个日夜的研究，ZHY 最终挑选出了 $n$ 部 Migos 的说唱作品，依次编号为 $1,2,\\dots,n$。他认为只要学习完这 $n$ 部作品，就可以成为更加优秀的说唱歌手。于是，他会","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10256"},"statements":[{"statement_type":"Markdown","content":"经过刻苦的训练，ZHY 终于成为了一名说唱歌手。但这天，说唱歌手 ZHY 看到了同行说唱组合 Migos 的作品，立刻意识到了自己的差距，于是他要学习 Migos 的说唱技巧，复刻 Migos 的成功。\n\n经过数个日夜的研究，ZHY 最终挑选出了 $n$ 部 Migos 的说唱作品，依次编号为 $1,2,\\dots,n$。他认为只要学习完这 $n$ 部作品，就可以成为更加优秀的说唱歌手。于是，他会从第 $1$ 部作品，按编号从小到大的顺序依次进行学习，学习完第 $n$ 部作品就结束学习。\n\n不过，说唱歌手 ZHY 的学习方式很特殊。对于每部作品，他只会听 $1$ 分钟。这种学习方式的问题是，对于第 $i$ 部作品，他在投入 $1$ 分钟后，有可能学习成功，也有可能会失败，具体地，如果 ZHY 学习的是作品 $i$，那么在他花一分钟的时间进行学习后：\n\n- 有 $P_i$ 的概率，ZHY 学习成功了，那么他会接着去学习作品 $i+1$（当然如果 $i=n$ 就直接结束学习）。\n- 有 $1-P_i$ 的概率，ZHY 学习失败了。不幸的是，ZHY 脑内的记忆还会因此产生混乱，导致他只会记住前 $x_i$ 部作品，即他必须从第 $x_i+1$ 部作品开始重新学习。\n\nZHY 在尝试了几次学习后，深受记忆混乱的困扰，于是向脑科学专家 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\n\\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$。\n\n现在，ZHY 对自己的学习能力有了充分了解，但刚才的尝试让他疲惫不堪，所以他决定休息 $1$ 秒，并希望你帮他计算一下他期望多少分钟可以结束学习。不过他意识到，自己如果每部作品只学固定的 $1$ 分钟是不够全面的，所以他决定更改一些作品他所会学习的那一分钟，这会导致他学习这一部作品的成功概率发生改变。具体地，现在 ZHY 提出了 $k$ 个要求，每个要求有两种可能：\n\n1. 修改某个作品 $i$ 学习成功的概率 $P_i$。\n1. 询问以当前的概率他学习完 $n$ 部作品期望要多少分钟。\n\n由于 ZHY 要休息，所以他找上了你，希望你来解决他的要求。对于他的每个第二种要求，你要告诉他期望时间对 $10^9+7$ 取模的结果。ZHY 给了你 $1$ 秒的时间，因为他只能休息这么久。\n\n## Input\n\n第一行三个整数 $n,m,k$。意思如题面所述。\n\n接下来 $n$ 行，每行两个正整数 $p_i,q_i$，表示 $P_i=\\frac{p_i}{q_i}$。\n\n接下来 $m$ 行，每行两个整数 $l_{i},r_{i}$。\n\n接下来 $k$ 行，每行都是以下两种格式的其中一种：\n\n- `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$ 均为正整数。\n\n- `2` 为查询操作。表示询问此时结束学习的期望时间是多少。对 $10^9+7$ 取模。\n\n## Output\n\n对于每个询问，输出一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n**本题使用捆绑测试。**\n\n| Subtask 编号 | $n$ | $m$ | $k$ | 特殊性质 |分值 |\n| :-----: | :-----: | :-----: | :-----: | :-----: | :-----: |\n| $0$ | $\\le 300$ | $\\le 300$ | $\\le 300$ | 无 | $11$ |\n| $1$ | $\\le 3000$ | $\\le 3000$ | $\\le 3000$ | 无 | $4$ |\n| $2$ | $\\le 10^5$ | $\\le 10^5$ | $\\le 1$ | B | $5$ |\n| $3$ | $\\le 10^5$ | $\\le 10^5$ | $\\le 1$ | 无 | $14$ |\n| $4$ | $\\le 10^5$ | $=0$ | $\\le 10^5$ | 无 | $19$ |\n| $5$ | $\\le 10^5$ | $\\le 10^5$ | $\\le 10^5$ | A | $19$ |\n| $6$ | $\\le 10^5$ | $\\le 10^5$ | $\\le 10^5$ | B | $8$ |\n| $7$ | $\\le 10^5$ | $\\le 10^5$ | $\\le 10^5$ | C | $10$ |\n| $8$ | $\\le 10^5$ | $\\le 10^5$ | $\\le 10^5$ | 无 | $10$ |\n\n以下的“区间”均指 $[l_i,r_i]$。\n\n特殊性质 A：保证对于 $\\forall i \\in [1,m]$，$r_i-l_i+1\\le 5$。\n\n特殊性质 B：保证这些区间两两的交 $\\le 1$。即对于 $\\forall i,j \\in [1,m]$ 且 $i\\ne j$，有 $r_i\\le l_j$ 或 $r_j\\le l_i$。\n\n特殊性质 C：保证这些区间不存在包含关系。即对于 $\\forall i,j \\in [1,m]$ 且 $i\\ne j$，有 $l_i>l_j$ 或 $r_i<r_j$。\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10256","tags":["线段树","洛谷原创","洛谷月赛","动态 DP","全局平衡二叉树"],"sample_group":[["3 1 3\n1 3\n2 3\n1 4\n2 3\n2\n1 2 4 5\n2","10\n9"],["2 1 1\n1 1\n1 2\n0 2\n2","4"],["2 1 1\n1 1\n1 2\n1 2\n2","3"]],"created_at":"2026-03-03 11:09:25"}}