/MARIO3 - Mario nhảy cột

              Uses Crt;
      Var n,i,j,k:longint; a,f:array[-10..100000] of longint;
      Begin
          readln(n);
          for i:=1 to n do read(a[i]);
          a[0]:=0; a[n+1]:=0;
          f[0]:=1; f[n+1]:=0;
          k:=1000000000;
          for i:=1 to n+1 do
           if a[i]=0 then
            begin
                for j:=i-1 downto i-3 do
                begin
                if a[j]=0 then f[i]:=(f[i]+f[j]) mod k;
                end;
                if a[i-1]=1 then f[i]:=(f[i]+f[i-1]) mod k;
                if a[i-2]=1 then f[i]:=(f[i]+f[i-2]) mod k;
            end
            else
           if a[i]=1 then f[i]:=(f[i]+f[i-1]) mod k
           else
           if a[i]=2 then f[i]:=0;
           writeln(f[n+1] mod k);
           readln;
      End.