集合运算总和

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定数轴上的 $n$ 条线段，第 $i$ 条线段为 $[l_i,r_i]$。令 $S_i$ 表示这条线段包含的所有整数点组成的集合。

对于集合 $A,B$，$A\cup B$ 表示并集，$A\cap B$ 表示交集，$A\oplus B$ 表示对称差。

令 $[\mathbin{op}_1,\mathbin{op}_2,\ldots,\mathbin{op}_{n-1}]$ 中每个运算均可独立选择 $\cup$、$\oplus$ 或 $\cap$。对全部 $3^{n-1}$ 种运算序列，求下列表达式的集合大小之和：

$$\left|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\cdots)\ \mathbin{op}_{n-1}\ S_n\right|.$$

答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$。

输出格式

输出一行一个整数，表示所求答案对 $998244353$ 取模后的结果。

样例输入 1

4
3 5
4 8
2 2
1 9

样例输出 1

162

样例输入 2

4
1 9
3 5
4 8
2 2

样例输出 2

102

数据范围

• $2\le n\le3\cdot10^5$；
• $0\le l_i\le r_i\le3\cdot10^5$。

子任务编号	分值	特殊限制
1	20	$n\le10$ 且所有 $r_i\le20$
2	40	$n\le2000$ 且所有 $r_i\le2000$
3		无特殊限制