/*
#include <iostream>

using namespace std;
*/

typedef long long ll;

int n;
int *a;
int b[501];
ll mod = 1e9+7;


ll mem[501][501];

ll brNacina(int l, int d)
{
    if(d - l + 1 == 4) return (a[l] + a[l+1] + a[l+2] + a[l+3])%2 == 1;
    if(mem[l][d] != -1) return mem[l][d];
    int brZ = (d - l + 1)/4;
    if((b[d] - b[l-1])%2 != brZ%2) return 0;

    //for(int i = 0; i < dub; i++) cout << "\t";
    //cout << "Pozvan za " << l << " " << d << " " << endl;
    ll rez = 0;

    for(int i = l + 1; l <= i && i <= d; i += 4)
    {
        for(int j = i + 1; l <= j && j <= d; j += 4)
        {
            for(int k = j + 1; l <= k && k <= d; k += 4)
            {
                if((a[i] + a[j] + a[k] + a[l]) % 2 == 1)
                {
                    //cout << "Validna trojka " << root << " " << i << " " << j << " " << k << endl;
                    ll a1 = 1, a2 = 1, a3 = 1, a4 = 1;
                    if(i-l != 1) a1 = brNacina(l + 1, i-1);
                    if(j-i != 1) a2 = brNacina(i + 1, j-1);
                    if(k-j != 1) a3 = brNacina(j + 1, k-1);
                    if(k != d) a4 = brNacina(k + 1,  d);
                    rez += (((((a1*a2)%mod)*a3)%mod)*a4)%mod;
                    if(rez > mod) rez -= mod;
                }
                //else cout << "Nije validna " << root << " " << i << " " << j << " " << k << endl;
            }
        }
    }
    //while(dub--) cout << "\t";
    //cout << "Ovako moze " << rez << endl;
    mem[l][d] = rez%mod;
    return rez%mod;
}

void precalc()
{
    for(int len = 4; len <= 8; len += 4)
    {
        for(int l = 1; l+len-1 <= n; l++)
        {
            int d = l+len-1;
            if(len == 4)
                mem[l][d] = ((a[l] + a[l+1] + a[l+2] + a[l+3]) % 2 == 1);
            else
            {
                mem[l][d] = 0;
                // poslednja cetvorka sama
                mem[l][d] += mem[l][d - 4] * mem[d - 3][d];
                // prva cetvorka sama, osim ako je len 8, jer tada je isto
                if(len != 8) mem[l][d] += mem[l + 4][d] * mem[l][l + 3];

                // duplo uracunate kad su obe same
                if(len > 8) mem[l][d] -= mem[l+4][d-4];

                // 2-2
                mem[l][d] += mem[l+2][d-2] * ((a[l] + a[l+1] + a[d-1] + a[d]) % 2 == 1);
                // prvi i tri poslednja
                mem[l][d] += mem[l+1][d-3] * ((a[l] + a[d-2] + a[d-1] + a[d]) % 2 == 1);
                // tri prva i poslednji
                mem[l][d] += mem[l+3][d-1] * ((a[l] + a[l+1] + a[l+2] + a[d]) % 2 == 1);
            }
        }
    }
}

int Zvezda(int nn, int *aa)
{
    n = nn, a = aa;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            mem[i][j] = -1;
    
    if(n == 4) return (a[1] + a[2] + a[3] + a[4])%2 == 1;
    b[0] = 0;
    b[1] = a[1];
    for(int i = 2; i <= n; i++)
        b[i] = b[i-1] + a[i];
    
    precalc();
    ll rez = 0;

    for(int i = 2; i <= n; i += 4)
    {
        for(int j = i+1; j <= n; j += 4)
        {
            int zbir = a[1] + a[i] + a[j], potrebna = 0;
            if(zbir == 0 || zbir == 2) potrebna = 1;
            for(int k = j + 1; k <= n; k += 4)
            {
                if(a[k] == potrebna)
                {
                    //cout << "\tValidna trojka " << root << " " << i << " " << j << " " << k << endl;
                    ll a1 = 1, a2 = 1, a3 = 1, a4 = 1;
                    if(i-1 != 1) a1 = brNacina(2, i-1);
                    if(j-i != 1) a2 = brNacina(i%n + 1, j-1);
                    if(k-j != 1) a3 = brNacina( j%n + 1, k-1);
                    if(k != n) a4 = brNacina(k%n + 1, n);

                    rez += (((((a1*a2)%mod)*a3)%mod)*a4)%mod;
                    if(rez > mod) rez -= mod;
                }
                //else cout << "\tNije validna " << root << " " << i << " " << j << " " << k << endl;
            }
        }
    }
    return rez%mod;
}

/*
int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 1; i <= n; i++) cin >> a[i];
    cout << Zvezda(n, a);
    return 0;
}
*/