配点 : $800$ 点

問題文

A, B, C からなる長さ $N$ の文字列 $S$ があります。

あなたは $S$ に対して、以下の操作を $0$ 回以上行うことができます。

• $S_i \neq S_{i + 1}$ である $i \sim (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$ で割った余りを出力せよ。

5
ABAAC

11

たとえば以下のように操作すると、文字列 $S$ として ACB が得られます。

• まず $i$ として $2$ を選ぶ。$S_2$ を C で置き換え、$S_3$ を削除するので $S$ は ACAC になる
• 次に $i$ として $3$ を選ぶ。$S_3$ を B で置き換え、$S_4$ を削除するので $S$ は ACB になる

50
AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB

256972022