/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
A, B, C からなる長さ N の文字列 S があります。
あなたは S に対して、以下の操作を 0 回以上行うことができます。
- S_i \neq S_{i + 1} である i ~ (1 \leq i \leq |S| - 1) を選ぶ。S_i を S_i, S_{i + 1} のいずれとも（
A,B,Cの中で）異なる文字で置き換え、S_{i + 1} を S から削除する
操作を 0 回以上行ったあとの S として、ありえるものの種類数を 10^9+7 で割った余りを出力してください。
制約
- 1 \leq N \leq 10^6
- S は
A,B,Cからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
操作を 0 回以上行ったあとの 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
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
Cand remove S_3, turning S intoACAC. - Then, choose i=3. We replace S_3 with
Band remove S_4, turning S intoACB.
Sample Input 2
50 AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB
Sample Output 2
256972022