有一个线性条带,分为 $$$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 31 2 1 33 3 1 21 3 2 3
输出复制
610038216
输入复制
2 31 2 1 22 3 1 2
输出复制
0
输入复制
8 51 3 1 21 5 1 61 4 4 55 5 1 74 5 1 24 5 2 53 3 2 71 2 1 3
输出复制
94391813
注意
在第一个示例中,概率等于 $$$\frac{5}{18}$$$。