点的子集

题目描述

二维平面上有一个由 $N$ 个点组成的集合 $S$，第 $i$ 个点的坐标为 $(x_i, y_i)$。这 $N$ 个点的 $x$ 坐标和 $y$ 坐标分别互不相同。

对于 $S$ 的非空子集 $T$，定义 $f(T)$ 为：各边平行于坐标轴且包含 $T$ 中所有点的最小矩形内所含的点的个数。更精确地说：

• 设 $T$ 所含点的 $x$ 坐标的最小值和最大值分别为 $a, b$，$y$ 坐标的最小值和最大值分别为 $c, d$，则 $f(T)$ 是满足 $a \leq x_i \leq b$ 且 $c \leq y_i \leq d$ 的 $1 \leq i \leq N$ 的个数。

请计算 $S$ 的所有非空子集 $T$ 的 $f(T)$ 之和。答案可能非常大，请输出除以 $998244353$ 的余数。

输入格式

输入按以下格式从标准输入给出：

$N$
$x_1$ $y_1$
$:$
$x_N$ $y_N$

输出格式

输出 $S$ 的所有非空子集 $T$ 的 $f(T)$ 之和除以 $998244353$ 的余数。

样例

3
-1 3
2 1
3 -2

13

设第 $1, 2, 3$ 个点分别为 $P_1, P_2, P_3$。$S = \{P_1, P_2, P_3\}$ 的非空子集有 $7$ 个，对应的 $f$ 值如下：

• $f(\{P_1\}) = 1$
• $f(\{P_2\}) = 1$
• $f(\{P_3\}) = 1$
• $f(\{P_1, P_2\}) = 2$
• $f(\{P_2, P_3\}) = 2$
• $f(\{P_3, P_1\}) = 3$
• $f(\{P_1, P_2, P_3\}) = 3$

这些值的和为 $13$。

4
1 4
2 1
3 3
4 2

34

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

7222

注意要输出和除以 $998244353$ 的余数。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq x_i, y_i \leq 10^9$
• $x_i \neq x_j (i \neq j)$
• $y_i \neq y_j (i \neq j)$
• 所有输入均为整数