移除机器人

题目描述

数直线上放置了 $N$ 个机器人,编号为 $1$ 到 $N$。机器人 $i$ 位于坐标 $X_i$,启动后会向正方向移动 $D_i$,移动结束的同时从数直线上移除。所有机器人的移动速度相同,大小可以忽略。

爱恶作剧的高桥君,只要数直线上还有机器人,就可以任意多次进行以下操作。(也可以一次都不进行。)

• 选择一个机器人并启动它。如果存在正在移动中的机器人,则不能进行此操作。

在机器人 $i$ 移动的过程中,如果接触到数直线上位于坐标 $X_i$ 以上、$X_i + D_i$ 未满范围内还残留着的另一个机器人 $j$,则机器人 $j$ 也会被启动并开始移动。该处理会递归地重复进行。

在高桥君重复操作之后,数直线上残留的机器人的组合可能有多少种?答案可能会非常大,请输出对 $998244353$ 取模的结果。

输入格式

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

$N$
$X_1$ $D_1$
$:$
$X_N$ $D_N$

输出格式

输出数直线上残留的机器人的组合数对 $998244353$ 取模的结果。

样例

2
1 5
3 3

3

数直线上残留的机器人组合可能有 $\{1, 2\}, \{1\}, \{\}$ 这 $3$ 种。

它们可以通过如下操作实现:

• 高桥君不启动任何机器人。此时机器人 $\{1, 2\}$ 残留。
• 高桥君启动机器人 $1$。此时机器人 $1$ 在移动过程中启动机器人 $2$,最终没有任何机器人残留。或者,高桥君先启动机器人 $2$ 再启动机器人 $1$,也可以达到没有任何机器人残留的状态。
• 高桥君启动机器人 $2$ 后结束操作。此时机器人 $\{1\}$ 残留。

3
6 5
-1 10
3 3

5

数直线上残留的机器人组合可能有 $\{1, 2, 3\}, \{1, 2\}, \{2\}, \{2, 3\}, \{\}$ 这 $5$ 种。

4
7 10
-10 3
4 3
-4 3

16

所有机器人都不会影响其他机器人。

20
-8 1
26 4
0 5
9 1
19 4
22 20
28 27
11 8
-3 20
-25 17
10 4
-18 27
24 28
-11 19
2 27
-2 18
-1 12
-24 29
31 29
29 7

110

注意要输出可能的组合数对 $998244353$ 取模的结果。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq X_i \leq 10^9$
• $1 \leq D_i \leq 10^9$
• $X_i \neq X_j$ ($i \neq j$)
• 输入均为整数