AT_arc110_e [ARC110E] Shorten ABC

[problemUrl]: https://atcoder.jp/contests/arc110/tasks/arc110_e `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 $ で割った余りを出力してください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^6 $ - $ S $ は `A`, `B`, `C` からなる長さ $ N $ の文字列 ### Sample Explanation 1 たとえば以下のように操作すると、文字列 $ S $ として `ACB` が得られます。 - まず $ i $ として $ 2 $ を選ぶ。$ S_2 $ を `C` で置き換え、$ S_3 $ を削除するので $ S $ は `ACAC` になる - 次に $ i $ として $ 3 $ を選ぶ。$ S_3 $ を `B` で置き換え、$ S_4 $ を削除するので $ S $ は `ACB` になる