解题思路

设第 $i$ 条线段出现的概率为

目标是求：最终每个格子都被恰好 $1$ 条线段覆盖的概率。

题目内容

有一条长度为 $m$ 的线段，被划分为从左到右编号为 $1$ 到 $m$ 的格子。

现在给出 $n$ 个线段。第 $i$ 个线段由四个整数 $l_i,r_i,p_i,q_i$ 描述，表示该线段会覆盖从 $l_i$ 到 $r_i$ 的所有格子(两端都包含)；以概率 $\frac{p_i}{q_i}$ 出现，并且所有线段是否出现 相互独立。

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

我们在模数 $998244353$ 下输出答案。设这个概率可以表示为最简分数 $\frac{x}{y}$，你需要输出

$x·y^{-1}mod998244353$，其中 $y$ 表示在模 $998244353$ 意义下的乘法逆元，即满足 $y·y^{-1}=1 (mod998244353)$ 的那个整数。

输入描述

第一行包含两个整数 $n,m (1≤n,m≤2×10^4)$，分别表示线段个数和格子个数。

第二行包含 $n$ 个整数，代表 $l_i$，即第 $i$ 条线段的左边界。

第三行包含 $n$ 个整数，代表 $r_i$，即第 $i$ 条线段的右边界。

第四行包含 $n$ 个整数。代表 $p_i$。

第五行包含 $n$ 个整数，代表 $q_i$。含义如下：$1≤p_i≤q_i<998244353$：第 $i$ 条线段存在的概率为 $\frac{p_i}{q_I}$。

保证所有线段是否出现相互独立。

输出描述

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

样例1

输入

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

输出

610038216

说明

对样例 $1$，可以计算得到“每个格子恰好被一个线段覆盖“的总概率为 $5/18$ 。

样例2

输入

2 3
1 2
2 3
1 1
2 2

输出

0

样例3

输入

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

输出

94391813