OMC233(E)

点数: 500

Writer: natsuneko

　各文字が $0$ または $1$ である文字列 $S$ に対して，以下の $2$ 種類の操作を考えます：

• $S$ の隣り合う $2$ 文字を選び，入れ替える
• $S$ の隣り合う $2$ 文字を選び，それらが同じ文字であるならば消去する．

これらを任意に組み合わせることで $S$ を空文字列にできるとき，必要な操作の回数の最小値を $f(S)$ とおきます．
　いま，$0$ と $1$ がそれぞれ $2000$ 文字ずつからなる長さ $4000$ の文字列全体の集合を $\mathcal{S}$ で表します．$f(S)=n$ なる $S\in \mathcal{S}$ の個数を $g(n)$ とおき，$g(n)$ が最大となる正整数 $n$ を $N$ としたとき，$Ng(N)$ を素数 $997$ で割った余りを求めてください．
　ただし，任意の $S\in \mathcal{S}$ に対して $f(S)$ が定義されること，そして $N$ が一意に存在することが保証されます．