当前没有测试数据。

D. Segments Covering

题目描述

有一个被划分为 $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$ 行，每行包含四个整数 $l_i$、$r_i$、$p_i$ 和 $q_i$（$1 \le l_i \le r_i \le m$；$1 \le p_i < q_i < 998244353$）。

输出格式

输出一个整数——每个单元格都被恰好一个线段覆盖的概率对 $998244353$ 取模的结果。

具体来说，概率可以表示为既约分数 $\frac{x}{y}$，你需要输出 $x \cdot y^{-1} \mod 998244353$ 的值，其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \equiv 1 \pmod{998244353}$ 的整数。

样例输入

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

样例输出

610038216

提示

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