← 返回题目列表

Codeforces · 2125/D

D. 段覆盖

中文机器翻译题面 查看原题

有一个线性条带,分为 $$$m$$$ 个单元格,从左到右编号为 $$$1$$$ 到 $$$m$$$。

您将获得 $$$n$$$ 段。每个分段由四个数字定义:$$$l$$$、$$$r$$$、$$$p$$$ 和 $$$q$$$ - 该分段涵盖从 $​​$$l$$$ 到 $$$r$$$ 的单元格,并以 $$$\frac{p}{q}$$$ 的概率存在(独立)。

你的任务是计算每个单元格被覆盖的概率 正是 一段。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$)。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含四个整数 $$$l_i$$$、$$$r_i$$$、$$$p_i$$$ 和 $$$q_i$$$ ($$$1 \le l_i \le r_i \le m$$$; $$$1 \le p_i \lt q_i \lt 998244353$$$)。

输出

打印一个整数 - 每个单元格恰好被一个段覆盖的概率,以 $$$998244353$$$ 为模。

形式上,概率可以表示为不可约分数 $$$\frac{x}{y}$$$。您必须打印 $$$x \cdot y^{-1} \bmod 998244353$$$ 的值,其中 $$$y^{-1}$$$ 是一个整数,使得 $$$y \cdot y^{-1} \bmod 998244353 = 1$$$。

示例

输入
复制

3 3
1 2 1 3
3 3 1 2
1 3 2 3

输出
复制

610038216

输入
复制

2 3
1 2 1 2
2 3 1 2

输出
复制

0

输入
复制

8 5
1 3 1 2
1 5 1 6
1 4 4 5
5 5 1 7
4 5 1 2
4 5 2 5
3 3 2 7
1 2 1 3

输出
复制

94391813

注意

在第一个示例中,概率等于 $$$\frac{5}{18}$$$。