No.2147 Tower of Hanoi Toy
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.
- Move disk \( 1 \) from A to C.
- Move disk \( 2 \) from B to A.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
tails