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≤N≤2000
入力
出力
条件を満たす操作の個数を 998244353 で割った余りを出力してください。
サンプル
条件を満たす操作の一例を示します。なお、挿入された 0 を赤色、隣り合って置き換えられた要素を青色で示しています。
- A=(0) の先頭に 0 を挿入します。操作後の A は (0,1) となります。
- A=(0,1) の末尾に 0 を挿入します。操作後の A は (0,0,0) となります。
この場合の答えは 2 です。
この場合の答えは 0 です。
条件を満たす操作での A の変化の一例を示します。
- (0),(0,1),(1,0,0),(1,1,0,1),(1,1,1,0,0),(1,0,0,0,0,0),(0,0,0,0,0,0,0)
答えを 998244353 で割った余りを求めてください。