respect:東大文系数学2021第2問改、東大文系数学2020第2問改

問題文

正の整数 $N$ が与えられます。次のような操作を考えます。

• まず、整数列 $A$ を持ちます。最初、これは $(0)$ です。
• $N-1$ 回次の操作を行います。
  • $A$ の好きな位置に $0$ を挿入し、その $0$ に隣り合う各要素を、$0$ ならば $1$ に、$1$ ならば $0$ に置き換える。

$N-1$ 回の操作として考えられるものは $N!$ 通りありますが、このうち操作を終えた後の $A$ の全ての要素が $0$ であるようなものの個数を $998244353$ で割った余りを求めてください。

制約

• $N$ は整数
• $2\leq N\leq 2000$

入力

N

出力

条件を満たす操作の個数を $998244353$ で割った余りを出力してください。

サンプル

3

2

条件を満たす操作の一例を示します。なお、挿入された $0$ を赤色、隣り合って置き換えられた要素を青色で示しています。

• $A=(0)$ の先頭に $0$ を挿入します。操作後の $A$ は $(\color{red}{0} ,\color{blue}{1} \color{black}{)}$ となります。
• $A=(0,1)$ の末尾に $0$ を挿入します。操作後の $A$ は $(0,\color{blue}{0} ,\color{red}{0} \color{black}{)}$ となります。

この場合の答えは $2$ です。

5

0

この場合の答えは $0$ です。

7

160

条件を満たす操作での $A$ の変化の一例を示します。

• $(0),(\color{red}{0},\color{blue}{1} \color{black}{)},(\color{blue}{1},\color{red}{0},\color{blue}{0} \color{black}{)},(1,\color{blue}{1},\color{red}{0},\color{blue}{1} \color{black}{)},(1,1,\color{blue}{1},\color{red}{0},\color{blue}{0} \color{black}{)},(1,\color{blue}{0},\color{red}{0},\color{blue}{0},\color{black}{0},0 \color{black}{)},(\color{red}{0},\color{blue}{0},\color{black}{0},0,0,0,0 \color{black}{)}$

1998

928752812

答えを $998244353$ で割った余りを求めてください。