競技プログラミングで有名なテクニックとして，偶奇を用いた反転があります．これをこの問題にも適用してみましょう．

具体的には，入力の文字列の偶数番目の文字だけA,B を反転させてみます．

すると行える操作は以下の \(2\) 種類になります．

• AAA \(\to\) A
• BBB \(\to\) B

こうするとあとはほぼ明らかです． 連続する A, B の部分について，その長さが \(0\) にならない限り \(2\) ずつ減らす操作ができることになります．

例えば AAAAA という部分があれば，AAAAA, AAA,A の \(3\) 通りが最終状態としてありえます．

よって，同じ文字が連続する部分についてその長さを \(L\) とすると，その部分の最終状態としてあり得るのは \(\operatorname{floor}((L+1)/2)\) とわかります．

同じ文字が連続する部分全てについて，最終状態は独立に選ぶことができます．よって上の値の積がこの問題の答えになります．

回答例(C++)