201104: [AtCoder]ARC110 E - Shorten ABC
Memory Limit:1024 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $800$ points
Problem Statement
We have a string $S$ of length $N$ consisting of A
, B
, and C
.
You can do the following operation on $S$ zero or more times:
- Choose $i$ $(1 \leq i \leq |S| - 1)$ such that $S_i \neq S_{i + 1}$. Replace $S_i$ with the character (among
A
,B
, andC
) that is different from both $S_i$ and $S_{i + 1}$, and remove $S_{i + 1}$ from $S$.
Find the number of distinct strings that $S$ can be after zero or more operations, and print the count modulo $(10^9+7)$.
Constraints
- $1 \leq N \leq 10^6$
- $S$ is a string of length $N$ consisting of
A
,B
, andC
.
Input
Input is given from Standard Input in the following format:
$N$ $S$
Output
Print the number of distinct strings that $S$ can be after zero or more operations, modulo $(10^9+7)$.
Sample Input 1
5 ABAAC
Sample Output 1
11
For example, the following sequence of operations turns $S$ into ACB
:
- First, choose $i=2$. We replace $S_2$ with
C
and remove $S_3$, turning $S$ intoACAC
. - Then, choose $i=3$. We replace $S_3$ with
B
and remove $S_4$, turning $S$ intoACB
.
Sample Input 2
50 AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB
Sample Output 2
256972022