#include <bits\stdc++.h>
#define MOD 1000000007
#define MAXN 507
using namespace std;
vector<int> v[MAXN][3];
long long dp[MAXN][MAXN];
int kj[4],n;
bool cr[MAXN];
void ncet(int b,int c,int s,int dk)
{
    int poc=dk-1;
    kj[b+c-1]=poc;
    if((c==1 && b==3) || (c==3 && b==1))
    {
        v[s][0].push_back(kj[1]);
        v[s][1].push_back(kj[2]);
        v[s][2].push_back(kj[3]);
    }
    for(int i=dk;i<n;i++)
    {
        if(cr[i] && ((c==0 && b<=3) || (c<3 && b<=1))) ncet(b,c+1,s,i+1);
        if(!cr[i] && ((b==0 && c<=3) || (b<3 && c<=1))) ncet(b+1,c,s,i+1);
    }
}
long long resi(int l,int r)
{
    if(l==r+1) return 1;
    if(dp[l][r]!=-1) return dp[l][r];
    dp[l][r]=0;
    for(int i=0;i<v[l][0].size();i++)
    {
        int u=v[l][i][0],vl=v[l][1][0],w=v[l][i][2];
        if(w>r) continue;
        long long a=resi(l+1,u-1),b=resi(u+1,vl-1),c=resi(vl+1,w-1),d=resi(w+1,r);
        dp[l][r]=(dp[l][r]+(((a*b)%MOD)*((a*b)%MOD))%MOD)%MOD;
    }
    return dp[l][r];
}
int Zvezda(int N, int A[])
{
    n=N;
    long long res=0;
    for(int i=0;i<n;i++) cr[i]=A[i+1];
    for(int i=0;i<n;i++)
    {
        if(cr[i]) ncet(0,1,i,i+1);
        else ncet(1,0,i,i+1);
    }
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) dp[i][j]=-1;
    return resi(0,n-1);
}