题目描述

一列に並んだ $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$ で割った余りを出力せよ。

题目大意

题目描述

有 $n$ 个点和 $k$ 个区间 , 数据保证区间之间没有重合部分 。 你现在在点 $1$ , 每一次可以走 $d$ 步 ( $d$ 为给定区间中的数 ) , 求走到终点的方案数对 $998244353$ 取模的结果

输入格式

共 $k+1$ 行

第一行为 $n$ 与 $k$ , 含义如上

接下来 $2$ 至 $k+1$ 行为 $k$ 个区间

5 2
1 1
3 4

4

5 2
3 3
5 5

0

5 1
1 2

5

60 3
5 8
1 3
10 15

221823067

提示

制約

• $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$ で割った余りを出力することに注意してください。