No.2147 ハノイの塔のおもちゃ
タグ : / 解いたユーザー数 50
作問者 :
tails
/ テスター :
👑 
p-adic
問題文
（最後の一文を読むだけで題意が取れます。）
Yuki さんの家に、孫の Sora ちゃんが遊びに来ています。 Sora ちゃんは、 Yuki さんの家にあるハノイの塔のおもちゃで遊ぶのが大好きです。
ハノイの塔のおもちゃは、 \(3\) 本の杭 A, B, C と、穴のあいた \(N\) 枚の円盤で構成されています。 円盤は、大きさが全て異なり、小さいものから順に \(1\) 番から \(N\) 番までの番号が付けられています。 円盤は杭に刺すことができ、後から刺した円盤はその杭に刺さっている中で一番上に積まれます。 また、杭からは、円盤を、一番上にあるものから 1 つずつ取り外せるようになっています。 初期状態において、円盤はすべて杭 A に刺さっていて、小さいものほど上になるように積まれています。
ハノイの塔のおもちゃは、次の「操作」を繰り返すことによって、遊ぶことができます。 なお、一度始めた「操作」を完了する前に次の「操作」を始めることはできません。
「操作」： 円盤が刺さっている杭を 1 つ選び、その杭に刺さっている円盤のうち一番上にあるものを、その杭から取り外す。 取り外した円盤を \(D\) とする。 次に、 \(D\) より小さい円盤が刺さっていない杭を 1 つ選び、その杭に \(D\) を刺す。
（同時に 2 枚以上の円盤を取り外した状態にはならないことに注意してください。）
Sora ちゃんは、初期状態から始めて「操作」を繰り返して無邪気に遊んでいましたが、何回かの「操作」をした後でふと気が付くと、初期状態への戻し方がわからなくて、悲しくなってしまいました。 そこで、やさしい Yuki さんは、かわいい Sora ちゃんのために、一緒に初期状態に戻してあげることにしました。
ハノイの塔のおもちゃの現在の状態が与えられますので、それを初期状態に戻すために必要な「操作」の回数の最小値を \( 10^9+7 \) で割った余りを出力してください。
入力
ハノイの塔のおもちゃの現在の状態が与えられます。
\(N\) \(S\)
\( 1 \le N \le 1000 \)
\( N \) は整数。
\( S \) は、 A, B, C の文字のみで構成される、長さ \( N \) の文字列。
\( S \) の \( i \) 文字目は、番号 \( i \) の円盤が刺さっている杭を表す。（ \( 1 \le i \le N \) ）
出力
ハノイの塔のおもちゃを初期状態に戻すために必要な「操作」の回数の最小値を \( 10^9+7 \) で割った余りを 1 行に出力してください。
サンプル
サンプル1
入力
3 ABA
出力
3
円盤は全部で \(3\) 枚あり、現在の状態において、 \(1\) 番の円盤は杭 A に、 \(2\) 番の円盤は杭 B に、 \(3\) 番の円盤は杭 A に刺さっています。
その状態から、以下の 3 回の操作で初期状態に戻すことができます。これより少ない操作ではできません。
- \( 1 \) 番の円盤を A から C に移動する。
- \( 2 \) 番の円盤を B から A に移動する。
- \( 1 \) 番の円盤を C から A に移動する。
サンプル2
入力
10 AAAAAAAAAA
出力
0
Sora ちゃんは、ハノイの塔のおもちゃが初期状態に戻っていることに気が付いていないだけでした。 Yuki さんは、そのことをそっと教えてあげました。
サンプル3
入力
10 BBBBBBBBBB
出力
1023
初期状態において、円盤はすべて「杭 A 」に刺さっていました。
サンプル4
入力
31 BBCCCAAACCBCBAABCBBCBCABACBBBBC
出力
123456789
\( 10^9+7 \) で割った余りを出力することを忘れないでください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。