Counting Sets

問題に与えられた条件を，集合 $X$ が『連続する自然数を要素として持たない』$\scriptsize ・・・(*)$ と言い換えると，より考察が進めやすくなるかもしれません．

$K \in \mathbb Z_+$ について $1$ 以上 $K$ 以下の正整数の集合に含まれる，ある部分集合が $\scriptsize (*)$ を満たすとき，それを $\scriptsize K$-valid な集合と呼びます．
$\scriptsize N$-valid な集合が何通りあるかを求めることがこの問題のゴールです．

$N \geq 2$ において $\scriptsize N$-valid な集合を構成するとき，$\scriptsize [N-1]$ -valid な集合に加えて，新たに正整数 $N$ を用いることができます．
$K \in \mathbb Z_+$ について $\scriptsize [K-1]$ -valid な集合のうち，正整数 $K$を挿入すると $\scriptsize K$-valid な集合になるものを $\scriptsize K$-completed な集合と呼ぶとすると，$\scriptsize [N-1]$ -valid な集合の個数に $\scriptsize N$-completed な集合の個数を足したものが，求めるべき答えです．

$\scriptsize N$-completed な集合が満たす条件を考えてみましょう．新たに正整数 $N$ を挿入してもなお $\scriptsize (*)$ を満たさなければなりませんから，要素として正整数 $N-1$ を持つことはできません．
また，$N-1$ を要素として持たないような $\scriptsize [N-1]$ -valid な集合ならば，必ず $\scriptsize N$-completed な集合である条件を満たします．
結果的に，この条件は $\scriptsize [N-2]$ -valid な集合が満たす条件と一致します．

したがって，$N \geq3$ において $\scriptsize N$-valid な集合の個数は，$\scriptsize [N-1]$ -valid な集合の個数と $\scriptsize [N-2]$ -valid な集合の個数とを足し合わせたものになります．
$\scriptsize 1$-valid な集合と $\scriptsize 2$-valid な集合はそれぞれ $2$ 通り，$3$ 通りとあるので，再帰的に計算を行うことで任意の $N(\geq1)$ について答えを求めることができました．

これは，動的計画法などの適切なアルゴリズムを用いることで十分高速に計算することが可能です．
$998244353$ で割った余りを出力することに注意してください．

---

実装例