本题的时空限制结合 OJ 性能以及未在赛时使用的 5 个官方数据，相对官方设置有所调整。

时间限制： 1.0 秒 2.0 秒

空间限制： 512 MB 1024 MB

题目背景

和其他许多同龄的小朋友一样，小 P 也喜欢玩手游抽卡。为了防止沉迷游戏影响学习，他只能在每个休息日的晚上玩一小时游戏。为了在这短暂的时间内赢得尽量多的分数，小 P 想让你帮他计算不同情况下，他可能获得的期望游戏分数。

题目描述

游戏中共有三类卡牌：SSR、SR 和 R。

在每一局游戏中，小 P 恰有 $n$ 次抽卡机会，其中第 $i$ 次有 $p_i$ 的概率抽到 SSR，$q_i$ 的概率抽到 SR，剩下 $1-p_i-q_i$ 的概率为 R。

SSR 卡牌共有三种，当小 P 抽到 SSR 类牌时，他会等概率地获得其中的一种。也就是说，他第 $i$ 次抽卡抽到特定的一种 SSR 的概率为 $\frac{p_i}{3}$。一旦小 P 抽齐三种 SSR，就会触发一次结算：如果此时他手中有 $S$ 张 SSR（可能有重复）和 $K$ 张 SR，则他将获得 $S^2+K$ 的分数。

结算后小 P 手中的卡牌会被清空，他将重复“抽卡——结算——清空”的过程直至 $n$ 次抽卡机会用完，过程中多次结算的分数会被累加。需要注意，如果第 $n$ 次抽卡后未触发结算，则此时小 P 手中剩余的卡牌不会产生任何分数。小 P 想知道，$n$ 次抽卡后总分数的期望是多少。

为了吸引玩家参与抽卡，游戏运营方还会举办 $m$ 次活动。每次活动中，运营方都会修改某一次抽卡的概率（一对 $p_i$ 和 $q_i$）；该修改仅在当前活动中生效，不会影响到其他活动。为了节省新活动研究攻略的时间，小 P 还需要你帮他算出每次活动中抽卡的分数期望。

输入格式

从标准输入读入数据。

第一行两个整数 $n,m$，表示小 P 有 $n$ 次抽卡机会，活动个数为 $m$，保证 $n,m\le 5\times 10^5$。

接下来 $n$ 行，每行有两个整数 $p_i,q_i$，其中第 $i$ 行为第 $i$ 次抽卡对应的两个概率。概率不用带百分号的百分数表示，即用满足 $0\le c\le 100$ 的整数 $c$，表示概率 $c\%$。

接下来 $m$ 行，每行有三个整数 $t,p',q'$ 描述一个活动，表示在该活动中将第 $t$ 次抽卡中的概率 $p_t,q_t$ 修改为 $p',q'$。

输出格式

输出到标准输出。

输出 $m+1$ 行，每行一个整数。

第一行为在不参与活动的情况下，小 P 总分数的期望；接下来 $m$ 行，为对应每次活动中，小 P 总分数的期望。

很显然，每个期望值都是有理数；但考虑到精度问题，你不能直接输出这个值。记所求的期望值为 $E$，你需要输出 $E\times 300^n$ 对 $10^9+7$ 取模的值（容易证明 $E\times 300^n$ 总是一个非负整数）。

3 0
20 40
10 20
30 40

324000

样例 1 解释

想要触发结算，必定小 P 三次均抽出 SSR，且互不相同，概率为 $0.2\times 0.1\times 0.3\times \dfrac{3!}{3^3}=\dfrac{1}{750}$，此时结算分数为 $3^2+0=9$，故总分数期望为 $\dfrac{3}{250}$。最后输出 $\dfrac{3}{250}\times 300^3=324000$。

4 1
20 40
20 30
30 40
20 30
2 10 20

686160000
441360000

样例 2 解释

不参与活动的结果为 $\dfrac{953}{11250}\times 300^4=686160000$。

3 2
20 40
10 20
20 30
1 10 20
3 30 40

216000
108000
324000

样例 3 解释

注意最后一次活动的概率是按照 $(20,40),(10,20),(30,40)$ 计算的（即与样例 1 的概率相同），各个活动互不影响。

5 0
10 30
10 30
10 30
10 30
10 30

981399671

样例 4 解释

$981399671$ 是 $47981400000$ 对 $10^9+7$ 取模的结果。

子任务

对于所有数据，保证 $1\le n\le 5\times 10^5,~0\le m\le 5\times 10^5,~0\le p\le 30,~p\lt q\le 70,~p+q\le 70,~1\le t\le n$。