　入れ替えの操作を行う際には，異なる $2$ 文字に対してのみ行うとしてよい．\
　初期状態から $n$ 回操作を（何らかの方法で）行った時点において，以下のように定める．

- 左から奇数文字目にある $1$ の個数を  $a_n$ とする．
- 左から偶数文字目にある $1$ の個数を  $b_n$ とする．

特に，$a=a_0, ~ b=b_0$ とおく．さらに，$c_n=|a_n-b_n|$ とおく．このとき，$n$ 回目に消去の操作を行うと $c_n=c_{n-1}$ が，$n$ 回目に入れ替えの操作を行うと $c_{n}=c_{n-1}\pm 2$ が成り立つから，$S$ を空文字列にするためには少なくとも
$$ \dfrac{c_0}{2} = 1000 - \min(a,b) $$
回の入れ替えの操作が必要である．また，消去の操作は必ず $2000$ 回である．\
　逆に，次のように操作すれば，評価の方法とあわせて考えることでこの下界が実現可能である：

- まず，消去の操作を可能な限り行う．これによって，（必要ならば左右を入れ替えることで）文字列が $0101\cdots 0101$ になったとしてよい．続いて，前から見て $4$ 文字の塊ごとに，$0101\to 0011\to 11\to \varnothing$ と操作する．

　$\min(a,b) = k$ をみたす $S \in \mathcal{S}$ は，$k = 1000$ のときは $({}\_{2000}\mathrm{C}\_{1000})^2$ 個，$k \lt 1000$ のときは $2 × ({}\_{2000}\mathrm{C}\_{k})^2$ 個ある．これにより $N = 3000 - 999 = 2001$ とわかり，$2001 ×  2 × ({}\_{2000}\mathrm{C}\_{999})^2$ を素数 $997$ で割った余りを求めればよい．これは Wilson の定理，あるいは Lucas の定理などを用いることにより，$\mathbf{636}$ と分かる．
公式解説
https://onlinemathcontest.com/contests/OMC233/editorial/8384
　各文字が $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$ が一意に存在することが保証されます．
<details>
<summary>$f(S)$ の例<\/summary>
　$S=011101$ の場合，空文字列を $\emptyset$ と表すことにすると，
$$011101\to0101\to0011\to11\to\emptyset$$
などとでき，$f(S)=4$ である．
<\/details>