分数: 800 点
问题陈述
我们有一个字符串 S 长度 N 组成 A, B,和 C.
您可以对 S 零次或多次:
- 选择 i (1 \leq i \leq |S| - 1) 这样 S_i \neq S_{i + 1}。更换 S_i 与字符(其中
A,B,和C) 与两者不同 S_i 和 S_{i + 1},并删除 S_{i + 1} 来自 S.
找出不同字符串的数量 S 可以在零次或多次操作之后,并打印计数模数 (10^9+7).
约束
- 1 \leq N \leq 10^6
- S 是一个长度为的字符串 N 组成
A,B,和C.
输入
输入由标准输入按以下格式给出:
N S
输出
打印不同字符串的数量 S 可以在零次或多次运算之后,模 (10^9+7).
示例输入 1
5 ABAAC
示例输出 1
11
例如,以下操作顺序依次 S 进入 ACB:
- 首先,选择 i=2。我们替换 S_2 与
C并删除 S_3, 车削 S 进入ACAC. - 然后,选择 i=3。我们替换 S_3 与
B并删除 S_4, 车削 S 进入ACB.
示例输入 2
50 AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB
示例输出 2
256972022