题目描述

公子光顺利当上吴王后，为了表彰功臣，建立了一套功绩评定体系。

在一维数轴上有 $n$ 条线段，第 $i$ 条线段的左端点为 $L_i$，右端点为 $R_i$。

定义一个合法非空集合为：

• 集合中任意两条线段不能相交（共用端点也算相交）
• 但可以是包含关系或完全不相交

定义一个集合的权值为：

• 集合中线段的最大嵌套层数
• 若线段 $x$ 被线段 $y$ 包含，当且仅当 $L_y < L_x$ 且 $R_y > R_x$

注意：

• 相同线段不算包含关系

现在问：

所有合法非空子集的权值之和是多少？

答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$（$1 \le n \le 200$）。

接下来 $n$ 行，每行两个整数 $L_i, R_i$（$1 \le L_i < R_i \le 10^9$）。

输出格式

输出一行一个整数，表示答案。

3
1 4
2 3
5 6

9

样例解释：

最大层级为 $1$ 的线段集合有：

$\{[1,4]\}, \{[2,3]\}, \{[5,6]\}, \{[1,4],[5,6]\}, \{[2,3],[5,6]\}$

最大层级为 $2$ 的线段集合有：

$\{[1,4],[2,3]\}$ 和 $\{[1,4],[2,3],[5,6]\}$

故答案为：

$5 + 2 \times 2 = 9$

5
6 7
5 8
4 9
3 10
2 11

80

3
1 2
1 3
2 3

3

3
2 3
1 4
1 4

7