题目描述

在一条被分成 $m$ 个格子的线段上，格子编号从左到右为 $1$ 到 $m$。

给你 $n$ 条线段。第 $i$ 条线段由四个数字 $l_i, r_i, p_i, q_i$ 定义：

• 它覆盖格子区间 $[l_i, r_i]$（包括端点）；
• 它以概率 $\tfrac{p_i}{q_i}$ 存在（各线段的存在相互独立）。

你的任务是计算“每个格子恰好被一条线段覆盖”的概率。

• 形式上，这个概率可以写成不可约分数 $\tfrac{x}{y}$。请你输出

其中 $y^{-1}$ 是 $y$ 在模 $998244353$ 下的乘法逆元（即 $y\cdot y^{-1}\equiv1\pmod{998244353}$）。

输入格式

• 第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le2\cdot10^5$）。

• 接下来 $n$ 行，第 $i$ 行包含四个整数

  $$ l_i,\;r_i,\;p_i,\;q_i \quad(1\le l_i\le r_i\le m,\;1\le p_i<q_i<998244353) $$

  分别表示第 $i$ 条线段的覆盖区间和存在概率 $\tfrac{p_i}{q_i}$。

输出格式

输出一个整数，表示“每个格子被恰好一条线段覆盖”这一事件的概率在模 $998244353$ 下的值。

样例输入1

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

样例输出1

610038216

样例输入2

2 3
1 2 1 2
2 3 1 2

样例输出2

0

样例输入3

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

样例输出3

94391813

说明

样例 $1$ 解释

• 在第一个样例中，答案对应的真实概率是 $\tfrac{5}{18}$。