長さ \(2N\) の正しい括弧列 \(S\) のスコアは、\(S\) の前 \(N\) 文字に含まれる ( の数 \(c\) の \(2\) 倍に等しいです。

前 \(N\) 文字から \(c\) 個の ( を取り出し、後 \(N\) 文字から \(c\) 個の ) を取り出すことで、\(S\) は長さ \(2c\) のよい文字列の部分列を含んでいることが確認できます。また、\(c\neq N\) であるとき、前から \(c + 1\) 文字目の ( が後 \(N\) 文字に含まれ、後から \(c + 1\) 文字目の ) が前 \(N\) 文字に含まれることから、\(S\) は長さ \(2c + 2\) のよい文字列の部分列を含んでいないことが示せます。

よって、長さ \(2N\) の正しい括弧列 \(S\) であって、\(S\) の前 \(N\) 文字に含まれる ( の数が \(K\) に等しいものの数を求めればよいです。

\(N\leq 2K\) であるとき、鏡像法などを用いて答えが \(\left(\binom{N}{K} - \binom{N}{K + 1}\right)^2\) であることが示せます。\(2K < N\) のときの答えは \(0\) です。

階乗などを時間計算量 \(O(\max(N))\) で前計算することで、テストケースあたり時間計算量 \(O(1)\) で答えを求めることができます。