Дистанционный практикум по программированию

Each programmer knows the puzzle “The Hanoi Tower”. We will briefly remind you the conditions of this task.

There are 3 pivots: A, B, C. Initially, n disks of different diameter are placed on the pivot A: the smallest disk is placed on the top and every next one is placed in an increasing order of their diameters. The second and the third pivots are still empty.

You have to move all the disks from pivot A to pivot B, using pivot C as an auxiliary.

By one step you can take off 1 upper disk and put it either on an empty pivot or on another pivot over a disk with a bigger diameter.

Almost all books on programming contain a recursive solution of this task. In the following example you can see the procedure, written in Pascal.

 

 

It is well known that the solution given above requires (2ⁿ–1) steps. Taking into account the initial disposition we totally have 2ⁿ combinations of n disks disposition between three pivots. Thus, some combinations don’t occure during the algorithm execution. For example, the combination «CAB» will not be reached during the game with n = 3 (herein the smallest disk is on pivot C, the medium one is on pivot A, the biggest one is on pivot B).

Write a program that establishes if the given combination is occurred during the game.

 

Input

The first line of an input file contains a single integer n – the number of disks, and the second line contains n capital letters (“A”, “B” or “C”) – the disposition of the n disks between the pivots. The first (leftmost) letter designates position (a pivot name) of the smallest disk, the second letter – position of the second lagest, and so on…

 

Output

The output file must contain “YES” or “NO” depending on the reachability of the disks disposition during the game.

 

Limitations

1 <=; n <=; 250

 

Example

Input	Output
3 ACB	YES

 

Input	Output
3 CAB	NO

 

All Rybinsk-2012 problems (in PDF)