1 //BZOJ 1088 2 //by Cydiater 3 //2016.8.26 4 #include <iostream> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <cmath> 9 #include <ctime>10 #include <cstdlib>11 #include <queue>12 #include <map>13 #include <iomanip>14 #include <cstdio>15 using namespace std;16 #define ll long long17 #define up(i,j,n)       for(ll i=j;i<=n;i++)18 #define down(i,j,n)     for(ll i=j;i>=n;i--)19 const int MAXN=1e5+5;20 const int oo=0x3f3f3f3f;21 inline ll read(){22       char ch=getchar();ll x=0,f=1;23       while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24       while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25       return x*f;26 }27 ll N,a[MAXN],f[MAXN][1<<3],ans=0;28 namespace solution{29       inline ll col(ll num){30             int cnt=0;31             if(num&(1<<1))cnt++;32             if(num&(1<<2))cnt++;33             return cnt;34       }35       void init(){36             N=read();37             up(i,1,N)a[i]=read();38       }39       void dp(){40             memset(f,0,sizeof(f));41             f[0][0]=1;f[0][4]=1;42             up(i,1,N)up(S,0,(1<<3)-1)if(f[i-1][S]>0){43                   int tmp=col(S);44                   if(a[i]-tmp==0)f[i][S>>1]+=f[i-1][S];45                   if(a[i]-tmp==1&&i<N)f[i][(S>>1)|(1<<2)]+=f[i-1][S];46             }47       }48       void output(){49             up(i,0,(1<<3)-1)ans+=f[N][i];50             cout<<ans<<endl;51       }52 }53 int main(){54       //freopen("input.in","r",stdin);55       using namespace solution;56       init();57       dp();58       output();59       return 0;60 }