AT_abc179_d [ABC179D] Leaping Tak

[problemUrl]: https://atcoder.jp/contests/abc179/tasks/abc179_d 一列に並んだ $ N $ マスから成るマス目があり、マスには左から順番に$ 1,\ 2,\ \ldots,\ N $ の番号がついています。 このマス目で暮らしている高橋君は、現在マス $ 1 $ にいて、後述の方法で移動を繰り返してマス $ N $ へ行こうとしています。 $ 10 $ 以下の整数 $ K $ と、共通部分を持たない $ K $ 個の区間 $ [L_1,\ R_1],\ [L_2,\ R_2],\ \ldots,\ [L_K,\ R_K] $ が与えられ、これらの区間の和集合を $ S $ とします。ただし、区間 $ [l,\ r] $ は $ l $ 以上 $ r $ 以下の整数の集合を表します。 - マス $ i $ にいるとき、$ S $ から整数を $ 1 $ つ選んで ($ d $ とする)、マス $ i\ +\ d $ に移動する。ただし、マス目の外に出るような移動を行ってはならない。 高橋君のために、マス $ N $ に行く方法の個数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ : $ $ L_K $ $ R_K $

高橋くんがマス $ 1 $ からマス $ N $ に行く方法の個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1 \leq\ K\ \leq\ \min(N,\ 10) $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - $ [L_i,\ R_i] $ と $ [L_j,\ R_j] $ は共通部分を持たない ($ i\ \neq\ j $) - 入力はすべて整数である ### Sample Explanation 1 集合 $ S $ は 区間 $ [1,\ 1] $ と区間 $ [3,\ 4] $ の和集合であり、$ S\ =\ \{\ 1,\ 3,\ 4\ \} $ です。 マス $ 5 $ へ移動する方法は次の $ 4 $ 通りが考えられます。 - マス $ 1,\ 2,\ 3,\ 4,\ 5 $ の順に移動する。 - マス $ 1,\ 2,\ 5 $ の順に移動する。 - マス $ 1,\ 4,\ 5 $ の順に移動する。 - マス $ 1,\ 5 $ の順に移動する。 ### Sample Explanation 2 $ S\ =\ \{\ 3,\ 5\ \} $ であり、そもそもマス $ 5 $ にたどり着けないので $ 0 $ を出力してください。 ### Sample Explanation 4 $ 998244353 $ で割った余りを出力することに注意してください。