#include <iostream>
#include <string.h>

using namespace std;

int n;

bool exista;

char sir[10005];
char v[10005];
    
void f(int poz)
{
     cout<<"f("<<poz<<") sir["<<poz<<"]="<<sir[poz]<<'\n';
     int contor=0;
     for(contor=0;contor<=poz;contor++)
        cout<<sir[contor]<<' ';
        cout<<endl;
   
   if(exista)
      return;  
   
   if(poz>n+1)
      return;
   
   if(sir[poz]=='1' || sir[poz]=='2' || sir[poz]=='3')
       return;
   
   if(sir[poz]==v[n])    
   if(poz==n+1)
      exista=true;
   
   
   
   if(sir[poz]=='A')
   {
      sir[poz+1]='1';
      f(poz+1);
      sir[poz+1]='2';
      f(poz+1);
      sir[poz+1]='3';
      f(poz+1);
      
      //sir[poz]='A'; ??                 
   }
   else if(sir[poz]=='B')
   {
      strcpy(sir+poz+3,sir+poz); //2=1
      sir[poz+1]='2';
      sir[poz+2]='B';
      f(poz+1);
      
      strcpy(sir+poz+6,sir+poz+3);
      sir[poz+1]='1';
      sir[poz+2]='A';
      sir[poz+3]='3';
      sir[poz+4]='A';
      sir[poz+5]='C';
   }
   else if(sir[poz]=='C')
   {
      sir[poz+1]='2';
      f(poz+1);
      
      strcpy(sir+poz+4,sir+poz);
      sir[poz+1]='3';
      sir[poz+2]='B';
      sir[poz+3]='C';
      f(poz+1);
      
      sir[poz+1]='1';
      sir[poz+2]='2';
      sir[poz+3]='A';
      f(poz+1);     
   }
     
     /*
   if(perla=='A')
   {
      f(poz+1,'1');
      f(poz+1,'2');
      f(poz+1,'3');              
   }     
   else if(perla=='B')
   {
     f(poz+1,'2');
     f(poz+2,'B');
     
     f(poz+1,'1');
     f(poz+2,'A');
     f(poz+3,'3');
     f(poz+4,'A');
     f(poz+5,'C');      
   }*/
}

int main()
{
    
    cin>>n;
    int i;
    for(i=0;i<n;i++)
    {
       cin>>v[i];                
    }
    
    sir[0]='A';
    f(0);
    sir[0]='B';
    f(0);
    sir[0]='C';
    f(0);
    
    cout<<exista<<endl;
    
    system("PAUSE");
    return 0;
}