AT_abc158_f [ABC158F] Removing Robots

[problemUrl]: https://atcoder.jp/contests/abc158/tasks/abc158_f 数直線上に、$ 1 $ から $ N $ の番号のついた $ N $ 個のロボットが置かれています。ロボット $ i $ は座標 $ X_i $ に存在し、起動すると $ D_i $ だけ正の方向に移動し、移動を終えると同時に数直線上から取り除かれます。全てのロボットの移動速度は同じで、大きさは無視できます。 イタズラ好きの高橋君は、数直線上にロボットが残っている限り、好きなだけ以下の操作を行うことができます。($ 1 $ 回も行わないことも可能です) - ロボットを $ 1 $ つ選び起動する。移動中のロボットが存在するときは行えない。 ロボット $ i $ が移動する過程で、数直線上の座標 $ X_i $ 以上 $ X_i\ +\ D_i $ 未満の範囲に残っている別のロボット $ j $ と接触したら、ロボット $ j $ も起動されて移動を開始します。この処理は再帰的に繰り返されます。 高橋君が操作を繰り返した後、数直線上に残っているロボットの組み合わせとして考えられるものは何通り存在するでしょうか。答えは非常に大きくなる場合があるので、$ 998244353 $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ D_1 $ $ : $ $ X_N $ $ D_N $

数直線上に残っているロボットの組み合わせとして考えられるものの個数を $ 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) $ - 入力は全て整数である ### Sample Explanation 1 数直線上に残っているロボットの組み合わせとしては、$ \{1,\ 2\},\ \{1\},\ \{\} $ の $ 3 $ 通りが考えられます。 これらは次のように操作すると実現されます。 - 高橋君はロボットを起動しない。このとき、ロボット $ \{1,\ 2\} $ が残ります。 - 高橋君がロボット $ 1 $ を起動する。このとき、ロボット $ 1 $ が移動する過程でロボット $ 2 $ を起動します。最終的にロボットは $ 1 $ つも残っていません。もしくは、高橋君がロボット $ 2 $ を起動した後ロボット $ 1 $ を起動しても、ロボットが残っていない状態にすることができます。 - 高橋君がロボット $ 2 $ を起動し、操作を終了する。このとき、ロボット $ \{1\} $ が残ります。 ### Sample Explanation 2 数直線上に残っているロボットの組み合わせとしては、$ \{1,\ 2,\ 3\},\ \{1,\ 2\},\ \{2\},\ \{2,\ 3\},\ \{\} $ の $ 5 $ 通りが考えられます。 ### Sample Explanation 3 どのロボットも他のロボットに影響しません。 ### Sample Explanation 4 組み合わせとして考えられるものの個数を $ 998244353 $ で割った余りを出力することに注意してください。