問題一覧 > 通常問題

No.2147 Tower of Hanoi Toy

レベル : / AI推定難易度 : 1225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 54
作問者 : 👑 tails / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 959 / 自分の提出
問題文最終更新日: 2022-12-19 16:43:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

Problem Statement

(You can grasp the task just by reading the last sentence.)

Sora, Yuki's grandchild, has come to visit Yuki's house. Sora loves playing with the Tower of Hanoi toy at Yuki's house.

The Tower of Hanoi toy consists of \(3\) pegs A, B, C and \(N\) disks with holes. The disks all have different sizes and are numbered from \(1\) to \(N\) in increasing order of size. A disk can be placed on a peg, and a disk placed later is stacked on top of all the disks on that peg. Also, disks can be removed from a peg one at a time, starting from the topmost one. In the initial state, all disks are on peg A, stacked so that smaller disks are higher.

The Tower of Hanoi toy is played by repeating the following "operation". Note that the next "operation" cannot be started before completing an "operation" that has already been started.

"Operation": Choose one peg that has a disk on it, and remove the topmost disk on that peg from the peg. Let \(D\) be the removed disk. Then, choose one peg that does not have any disk smaller than \(D\) on it, and place \(D\) on that peg.

(Note that two or more disks are never in a removed state at the same time.)

Starting from the initial state, Sora was playing innocently by repeating "operations", but after some "operations" she suddenly noticed that she did not know how to return it to the initial state, and became sad. So kind Yuki decided to help adorable Sora return it to the initial state together.

Given the current state of the Tower of Hanoi toy, output the minimum number of "operations" required to return it to the initial state, modulo \( 10^9+7 \).

Input

The current state of the Tower of Hanoi toy is given.

\(N\)
\(S\)

\( 1 \le N \le 1000 \)
\( N \) is an integer.

\( S \) is a string of length \( N \) consisting only of the characters A, B, C.
The \( i \)-th character of \( S \) represents the peg on which disk \( i \) is placed. ( \( 1 \le i \le N \) )

Output

Output on one line the minimum number of "operations" required to return the Tower of Hanoi toy to the initial state, modulo \( 10^9+7 \).

Sample

Sample 1
Input
3
ABA
Output
3

There are \(3\) disks in total, and in the current state, disk \(1\) is on peg A, disk \(2\) is on peg B, and disk \(3\) is on peg A.

From that state, the initial state can be restored with the following 3 operations. It cannot be done with fewer operations.

  1. Move disk \( 1 \) from A to C.
  2. Move disk \( 2 \) from B to A.
  3. Move disk \( 1 \) from C to A.
Sample 2
Input
10
AAAAAAAAAA
Output
0

Sora simply had not noticed that the Tower of Hanoi toy was back in the initial state. Yuki gently let her know.

Sample 3
Input
10
BBBBBBBBBB
Output
1023

In the initial state, all disks were on "peg A".

Sample 4
Input
31
BBCCCAAACCBCBAABCBBCBCABACBBBBC
Output
123456789

Do not forget to output the remainder modulo \( 10^9+7 \).

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。