407409: GYM102785 E Hanoi Tower

It has become a good tradition in programming competitions to solve the problem of Hanoi Tower.

Let us briefly recall the rules of this puzzle game.

There are three rods: $$$A$$$, $$$B$$$, $$$C$$$. Initially, $$$N$$$ disks of different diameters are placed on the source rod $$$A$$$: the smallest disk is at the top, and then come other disks as the diameter increases. The second and third rods are empty so far.

You want to move all the disks from the source rod $$$A$$$ to the resultant rod $$$B$$$, using the third rod $$$C$$$ as an auxiliary. In one move, it is allowed to take one (necessarily upper) disk and put it on another rod, possibly empty. Moreover, a disc of a larger diameter can not be placed on a smaller disc.

Many programming textbooks provide a solution to this puzzle.

Procedure Hanoi (X, Y, Z: char; N: integer);
Begin
 If N>0 then 
    Begin
       Hanoi (X, Z, Y, N-1);
       Writeln('Disk ', N, ' from ', X, ' to ', Y);
       Hanoi (Z, Y, X, N-1)
    End
End;

Associate Professor P. from the city of R., preparing for the programming championship, decided to warm up and began to manually shift the disks of Hanoi Tower . (For this, he used rings from a children's pyramid and three rods taken from his granddaughter.)

At some point, the granddaughter, offended by her grandfather, selected a part of the rings, without touching the source rod with the strung discs-rings.

Help the assistant professor and calculate the minimum possible number of moves he has managed to make if the current location of the disks on the source rod is known.

Disk movements are performed using the standard algorithm described in the procedure above. The combination of disks specified in the input file is guaranteed to be achievable.

The first line contains a single integer $$$N$$$ - the initial number of disks ($$$1\leq N\leq 100$$$).

The second line of the file contains $$$N$$$ characters '0' and '1'. The symbol in the $$$i$$$-th position indicates whether a disk with the number $$$i$$$ is present (specified by the '1' sign) or not (specified by the '0' sign) on the initial rod at the moment of interruption into the game.

The output file must contain one integer in binary form without the preceding zeros - the minimum possible number of moves, after which the disks on the source rod are placed in a specified way.

3
111

0

3
001

10

5
00000

10000