A,B,C をそれぞれ \(0,1,2\) に変換します．

包除原理を使います． 「禁止パターンになっている連続する \(3\) 文字」の位置をいくつか決め打ったとします． すると，\(i\) 番目の文字 \(+1 \equiv (i+1)\) 番目の文字 \(\mod 3\) という制約がいくつか登場します． この制約が課されている \(i\) の連続区間を考えると，文字列がいくつかの区間に分割されます．

分割した後の区間の長さを \(L_1,L_2,\cdots,L_k\) とおきます． \((L_1,L_2,\cdots,L_k)\) を一つ決めたときの数え上げ問題を考えます．

まず，決められた \(L_i\) について，その \(L_i\) を達成するような，「禁止パターンになっている \(3\) 文字」の位置の集合を考え，それらの包除原理の係数の総和を考えます．これは以下の値になります．

• \(L_i \equiv 1 \mod 3\) のとき：\(1\)
• \(L_i \equiv 2 \mod 3\) のとき：\(0\)
• \(L_i \equiv 0 \mod 3\) のとき：\(-1\)

これは帰納法で確認できます．

\((L_1,L_2,\cdots,L_k)\) が与えられたとき，それを満たすように文字列を作る方法が何通りあるかを考えます．

まず，\(L_i \equiv 0\) の部分を考えると，これは \(0,1,2\) を同数ずつ含み，その並べ方は \(3\) 通りだけだとわかります． 次に，\(L_i \equiv 1\) の部分には，\(0,1,2\) の中の \(1\) つが他の \(2\) つよりもちょうど \(1\) 個多く含まれています．どの文字が多いかを決めてしまえば，その並べ方は一意に定まります．

これで \(L_i\) を決めた場合の数え上げは解けました． 次に，\(L_i\) を全通り試して総和を取ることを考えます． \(L_i\) を \(3+3+3+\cdots+3(+1)\) と分解し，\(1,3\) を並べた列 \(z\) を作ることを考えます．

この \(z\) に含まれる \(3\) の個数を決め打って，その \(z\) に対応する値を数えてみます．

\(z\) の末尾が \(1\) のケースを考えます． この時，残りの \(3,1\) の並び方によらず，対応する \(L_i\) すべてについての数え上げができます． 具体的には，\(z\) に含まれるそれぞれの \(3\) について，右の項と”連結”(同じ \(L_i\) に含まれることにする)するか否かを選ぶことを考えます． 連結する場合の係数は \(1\)，連結しない場合の係数は \(-3\) になるので，合わせると \(-2\) の係数がかかっていることになります． よって，\(1,3\) の並べ方に依らず，\((-2)^{z \text{に含まれる} 3 \text{の個数}}\) をかけることで数え上げが解けます．

\(z\) の末尾が \(3\) のケースも同様に処理できます．

よって，この問題は \(O(A+B+C)\) で解けます．

解答例(c++)