有 $n$ 个人在投票，候选人是 A ， B 。每个人都选择投给了 A 或 B 其中一位。

投票顺序是从第 $2$ 个人到第 $n$ 个人，第一个人可以在任意一个人投完票后选择投票（也可以是第一个）。

每个人投完票有三种结果：

• 结果 A ： 现在投给 A 的票数最多。
• 结果 B ： 现在投给 B 的票数最多。
• 结果 C ： 现在投给 A,B 的票数一样多。

把每次每人投完票的结果记录下来，形成一个长度为 $n$ 的序列。问最终生成的序列有多少种不同的可能？