给出四个大写字母 $c_{AA}$、$c_{AB}$、$c_{BA}$、$c_{BB}$ 和一个初始字符串 $s=AB$ ，每次操作可以选择字符串中相邻的两个字母 $s_i$、$s_{i+1}$ 并按下列规则在两个字母之间插入一个新的字母。

• 若 $s_i=A$ 且 $s_{i+1}=A$，则在两者之间插入字母 $c_{AA}$。
• 若 $s_i=A$ 且 $s_{i+1}=B$，则在两者之间插入字母 $c_{AB}$。
• 若 $s_i=B$ 且 $s_{i+1}=A$，则在两者之间插入字母 $c_{BA}$。
• 若 $s_i=B$ 且 $s_{i+1}=B$，则在两者之间插入字母 $c_{BB}$。

保证 $c_{AA}$、$c_{AB}$、$c_{BA}$、$c_{BB}$ 均为 $A$ 或 $B$。

求当 $s$ 的长度被添加至 $n$ 后，所有可能的字符串共有多少种？

样例一：可能出现的有 ABAB 和 ABBB。

样例二：只可能出现 ABBBB...BBBB 一种。