まずは条件を整理する。
インデックス があって（
） 、
から
両方を含むことはできないので明らかに0通り。
までの条件が「1」で
までの条件が「2」のとき
以上から答えが「0」のときは予め出力して処理を打ち切っておく。
上の条件を含まない時、
よって が始点になる条件は、「 最後の条件1のインデックス」と「最初の条件2のインデックス」だけが必要になるので変換しておく。
解法
最後に「0」になったインデックスと、最後に「1」になったインデックスを保存してDPをする。
dp[i][j][k] = i番目までみて、最後に「0」になったインデックスがj、最後に「1」になったインデックスがkとする。
遷移は次に「next = 」どちらにするかを試して、条件に違反しないなら
dp[i+1][nj][nk] += dp[i][j][k]
（nj,nkはnextの値によって最後の のインデックスに更新する）
で条件が
あるので遷移も
かかかって、全体で
。
実装上ではインデックス0を「」を使用していない状態とした。
よって初期化は dp[0][0][0]=1 。
条件に違反しないかの判定
（以後インデックス0は未使用状態を表すので1-indexedになっている）
例えば、 ,
のとき「****0111」となっている（＊は
どちらでもよい）。
ここで （xは今更新してようとしているインデックス）として、
から
までが「条件1」とすると、
のとき明らかに2種類含むので不適。
なので次に採用する値next が「0」なら不適（今決めようとしている一つ前のインデックスの状態はj,kの大きい方になってるいる）。
「条件2」の判定は「条件1」の逆になる（連続しないなら2種類の数字を含む）
j,kの大小と、0（未使用）のときも含めてうまく書く。
以上を実装してAC。
