题目描述

$Sandy\ Duck$ 现在正在满天繁星下发呆，看见了天上一部分区域的 $n$ 颗星星。

$Sandy\ Duck$ 用翅膀比划着建立了一个平面直角坐标系，并将星星按照横坐标（假定每颗星星横坐标不相同）从小到大编号 $1\sim n$ 。

但是由于观测不清，无法知道确切纵坐标，只知道 $i$ 号星星的纵坐标 $a_i$ 是区间 $[l_i,r_i)$ 内的一个均匀随机实数。

$Sandy\ Duck$ 希望将这一块天空划分为一整个树状星座。具体地，星座构成一棵二叉树的结构，对于 $i$ 号星星：

⋆ $i$ 号星星的左儿子的标号为满足下列条件且最大化对应的 $a_j$ 的 $j$ 。 $1$ . $1 \le j < i$ 。 $2$ . $a_j < a_i$ 。 $3$ . $j$ 到 $i$ 的星星的纵坐标均不超过 $max\{a_j , a_i\}$ 。 特别地，如果没有 $j$ 满足这样的条件，则它没有左儿子。

⋆ $i$ 号星星的右儿子的标号为满足下列条件且最大化对应的 $a_j$ 的 $j$ 。 $1$ . $i < j \le n$ 。 $2$ . $a_j < a_i$ 。 $3$ . $i$ 到 $j$ 的星星的纵坐标均不超过 $max\{a_i, a_j\}$ 。 特别地，如果没有 $j$ 满足这样的条件，则它没有右儿子。

在这样的意义之下，星座对应的树自然也有了"根"。 $Sandy\ Duck$ 认为，星座的复杂程度取决于每颗星星在星座中的位置。具体地，它定义星座上某颗星星的深度为到“根”的最短路径经过的边数，星座的复杂程度为所有星星的深度之和。

现在，它想问一问你，星座的复杂程度的期望是多少呢？由于 $Sandy\ Duck$ 讨厌无穷无尽的小数，它只需要你告诉它答案对 $998244353$ 取模之后的结果。

【提示】 考虑 $n$ 个格子均匀分布在某个区间的连续随机变量 $X_1,X_2,\ldots ,X_n$ 的时候，我们可以认为存在两个变量相同的概率为 $0$ 。

输入格式

第一行一个正整数 $n$ ，表示星星的个数。 接下来 $n$ 行，第 $i$ 行两个正整数 $l_i, r_i$ ，表示 $i$ 号星星的纵坐标为 $[l_i, r_i)$ 之中的随机实数。

输出格式

输出仅一行一个非负整数，表示星座的复杂程度的期望。

数据范围

设 $m=\max_{1\le i\le n}r_i$ 。

对于所有测试点： $1\le n\le 300$ ，且 $\forall 1\le i\le n,1\le l_i < r_i\le 998244352$ 。

每个测试点的具体限制见下表：

测试点编号	$n \le$	$m \le$	特殊限制
$1\sim 4$	$6$	$5$	无
$5\sim 6$	$9$	$998244352$	所有 $[l_i,r_i]$ 全部相等
$7\sim 8$		$20$	无
$9\sim 10$		$998244352$
$11\sim 15$	$100$
$16\sim 20$	$300$

输入样例 1

3
1 3
1 3
1 3

输出样例 1

665496238

输入样例 2

3
1 2
1 2
1 3

输出样例 2

831870297

样例解释

样例 $1$ ：

此时， $a_1,a_2,a_3$ 均在同一区间 $[1,3)$ 中均匀分布。

由【提示】部分，我们可以转而考虑 $a_1,a_2,a_3$ 的严格大小关系，并用一个排列 $p\in S_3$ 来表示这种大小关系。 $\forall j\neq k,p_j > p_k\Leftrightarrow a_j > a_k$ 。

那么，每一种排列的出现概率均为 $\frac{1}{3!}=\frac 1 6$ ，考察每种排列的情况下，星座的复杂程度：

$p=\{1,2,3\}$ ，复杂程度为 $3$ 。 $p=\{1,3,2\}$ ，复杂程度为 $2$ 。 $p=\{2,1,3\}$ ，复杂程度为 $3$ 。 $p=\{2,3,1\}$ ，复杂程度为 $2$ 。 $p=\{3,1,2\}$ ，复杂程度为 $3$ 。 $p=\{3,2,1\}$ ，复杂程度为 $3$ 。

因此，复杂程度的期望为 $\frac{1}{6}(3\times 4+2\times 2)=\frac 8 3$ ，对 $998244353$ 取模之后的结果为 $665496238$ 。

样例 $2$ ：

按照 $a_3$ 的取值范围来讨论：

$a_3\in [1,2)$ ，发生概率为 $\frac 1 2$ ：这中情况在【样例 $1$ 】中已经讨论过，期望为 $\frac 8 3$ 。

$a_3\in [2,3)$ ，发生概率为 $\frac 1 2$ ：此时必然有 $a_3 > a_1,a_3 > a_2$ 。我们接着考虑可能的排列 $p$ （每种排列出现概率均为 $\frac 1 2$ ）：

$p=\{1,2,3\}$ ，复杂程度为 $3$ 。

$p=\{2,1,3\}$ ，复杂程度为 $3$ 。

因此，所有情况中，复杂程度的期望为 $\frac{1}{2}\times \frac 8 3+\frac 1 2\times (\frac 3 2 +\frac 3 2)=\frac {17} 6$ ，对 $998244353$ 取模之后的结果为 $831870297$ 。