答えが非零になる数列 \(S\) について、 \(S\) の各要素を順に並べた列を正規表現で表すと \((3*2)*3*2*1 ?\) となります。ここで、 \(*\) は直前のものを \(0\) 回以上繰り返すこと、 \(?\) を直前のものを \(0\) 回または \(1\) 回出現することを表すとします。

まずはより単純な場合を考えます。

\(S = 3*\) である場合

\(S\) に含まれる \(3\) の個数を \(p\) とすると、 \(S\) を生成する 1, 2 からなる数列 \(A\) は以下を満たします。

• 1 が \(p\) 個、 2 が \(p\) 個現れる
• 1 のprefix sumが 2 のprefix sumの個数 \(+1\) 以下である

このような数列の個数は \((0,0)\) から \((p, p)\) へ \(y = x+1\) より上に行かないような最短経路の数なので \(\binom{2p}{p} - \binom{2p}{p+2}\) となります。

\(S = 3*2*1?\) である場合

\(2\) は 1 を \(2\) つ取り除いて生成する場合と、 2 を \(1\) つ取り除いて生成する場合があります。ここで、 2 を \(1\) つ取り除いて \(2\) を生成した後に 1 が取り除かれることはないです。また、 \(3 *\) を生成する数列が \(S\) を生成する数列のprefixとなります。

\(A\) の末尾に \(1\) が含まれる場合

\(2*\) は全て 1 を \(2\) つ取り除いて生成されるしかないので \(3 *\) を生成する数列の末尾に必要な数の \(1\) を追加すればよいです。

\(A\) の末尾に \(1\) が含まれない場合

末尾に \(2\) が \(q\) 個あるとします。先頭 \(i\) 個は 1 を \(2\) つ取り除いて生成し残りの \(q-i\) 個 は 2 を取り除いて生成されるとした場合、 \(i > 0\) のときは \(1\) が \(2i\) 個続き、 \(2\) が \(q-i\) 個続いた数列が生成列のsuffixとなります。一方で \(i = 0\) のときは \(2\) の個数が \(q\) 個増えるため、 \(S\) を生成する数列の個数は \((0,0)\) から \((p+q,p)\) へ \(y=x+1\) より上に行かないような最短経路の数となり \(\binom{2p + q}{p} - \binom{2p + q}{p + q + 2}\) となります。

\(S = (3*2)3*2*1?\) である場合

\(S\) が \(3 * 2 * 1?\) で表現できない場合を考えます。 \((3*2)\) の部分を生成する部分列は、 \(3*\) を生成する数列の末尾に 1 を \(2\) つ追加したものになります。末尾で 1 が \(2\) つ連続しているため \(S = (3*2)3*2*1?\) を生成する数列 \(A\) において、\((3*2)\) を生成する部分列と \(3*2*1?\) を生成する部分列はそれぞれ連続部分列となり重なりません。よってそれぞれ独立に数え上げて積を取ればよいです。

\(S = (3*2)*3*2*1?\) の場合

同様に \(S\) を生成する数列 \(A\) において \((3*2)*\) のそれぞれの \((3*2)\) や \(3*2*1?\) を生成する部分列は連続部分列となり重なっていないので独立に数え上げれば良いです。

以上より \(O(N)\) でこの問題が解けました。