配点 : 100 点
問題文
1 减去 N 有 N 开关。所有开关现已关闭。
从现在开始,按任意顺序切换。 1 你一一按下,但每个开关都坏了。具体来说,开关 i 按
它需要 T_i 秒,当你按下它时,它的行为如下:
- 確率 \frac{A_i}{B_i} 将其打开。 所有
- 確率 1 - \frac{A_i}{B_i} 在 N 开关均关闭。
每次按下开关时,都会独立选择是否打开开关。此外,按下一个开关时,无法按下另一个开关。
您的目标是尽快打开所有功能。正确按下所有开关后打开所有开关所需的预计秒数 查找 \bmod\ 998244353 。
期待値 \bmod\ 998244353 的定义
可以证明期望的期望值始终是有理数。另外,在这个问题的约束下,我们可以将该值转换为不可约分数 当表示为 \frac{P}{Q} 时, 也可以证明Q \neq 0 \pmod{998244353} 。因此,R \times Q = P \pmod{998244353},0 \le R < 998244353 的整数 选择 R 是唯一确定的。这个 请回答 R 。
制約
- 1 \le N \le 2 \times 10^5
- 1 \le T_i \le 10^6
- 1 \le A_i \le B_i \le 10^6
入力
输入是按以下格式从标准输入给出的。
N T_1 A_1 B_1 T_2 A_2 B_2 ⋮ T_N A_N B_N
出力
请打印答案。 到达
入力例 1
2 3 3 5 2 4 7
出力例 1
831870305
操作顺序的示例如下。 (此操作顺序不一定能达到最佳效果。)
- 开关 按住 1 该值应乘以 3 秒。开关 1 已打开。
- 开关 按住 2 该值应乘以 2 按住几秒钟。所有开关均关闭。
- 开关 按住 2 该值应乘以 2 秒。开关 2 已打开。
- 开关 按住 1 该值应乘以 3 秒。开关 1 已打开。
在这一系列操作中,所花费的时间是 10 秒,并且操作以这种方式进行的概率是 \frac{3}{5} \times \frac{3}{7} \times \frac{4}{7} \times \frac{3}{5} = \frac{108}{1225} 。
另外,在这种情况下,正确按下时打开所有开关所需的秒数的预期值为 \frac{65}{6} 秒。
入力例 2
5 2 5 9 6 4 7 1 9 14 17 8 13 10 4 11
出力例 2
914017655
入力例 3
8 6 2 8 3 1 8 5 30 71 7 9 58 6 4 7 6 9 25 2 8 67 6 6 55
出力例 3
923892723