← 返回题目列表

AtCoder · arc110_e

E. 缩短 ABC

中文机器翻译题面 查看原题

分数: 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