#include <bits/stdc++.h>
#define mid (l+r)/2
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
#define fi first
#define se second
#define pii pair<int,int>
#define lld long long
#define INF 1000000000
#define LINF 1000000000000000000LL
#define EPS 1e-9
#define PRINT(x) cerr<<#x<<"="<<x<<endl;
#define MAXN 510
#define MOD 1000000007
using namespace std;
lld dp1[MAXN][MAXN]; ///pocetak, duzina, sa pocetka do kraja
lld dp[MAXN][MAXN]; ///pocetak, duzina, kako god
int cnt[2], n;
bool a[MAXN];
/*inline bool valid(int idx1, int idx2, int idx3, int idx4) {
    cnt[0] = cnt[1] = 0;
    cnt[a[idx1]]++;
    cnt[a[idx2]]++;
    cnt[a[idx3]]++;
    cnt[a[idx4]]++;
    return ((cnt[0] == 3 && cnt[1] == 1) || (cnt[0] == 1 && cnt[1] == 3));
}*/
inline int translate(int K) {
    if(K > n) K -= n;
    return K;
}
int Zvezda(int N, int* A) {
    for(int i = 0; i < MAXN; i++) dp[i][0] = dp1[i][0] = 1;

    n = N;
    for(int l = 4; l <= N; l+=4) {
        for(int i = 1; i <= N; i++) {
            int d = (i+l-1 > N ? i+l-1-N:i+l-1);
            if(A[i] != A[d]) {
                for(int i1 = 0; i1 < l; i1 += 4) {
                    for(int i2 = 0; i2 < l-i1-2; i2 += 4) {
                        int idx2 = i+i1+1;
                        int idx3 = i+i1+i2+2;
                        if(A[idx2] == A[idx3]) {
                            lld rez = dp[i+1][i1]*dp[idx2+1][i2];
                            if(rez >= MOD) rez %= MOD;
                            rez *= dp[idx3+1][l-4-i1-i2];
                            //if(rez >= MOD) rez %= MOD;
                            dp1[i][l] += rez;
                            if(dp1[i][l] >= MOD) dp1[i][l] %= MOD;
                        }
                    }
                }
            } else {
                for(int i1 = 0; i1 < l; i1 += 4) {
                    for(int i2 = 0; i2 < l-i1-2; i2 += 4) {
                        int idx2 = i+i1+1;
                        int idx3 = i+i1+i2+2;
                        if(A[idx2] != A[idx3]) {
                            lld rez = dp[i+1][i1]*dp[idx2+1][i2];
                            if(rez >= MOD) rez %= MOD;
                            rez *= dp[idx3+1][l-4-i1-i2];
                            //if(rez >= MOD) rez %= MOD;
                            dp1[i][l] += rez;
                            //dp1[i+N][l] += rez;
                            if(dp1[i][l] >= MOD) dp1[i][l] %= MOD;//, dp1[i+N][l] %= MOD;
                        }
                    }
                }
            }
            for(int i1 = 4; i1 <= l; i1 += 4) {
                lld rez = dp1[i][i1]*dp[i+i1][l-i1];
                //if(rez >= MOD) rez %= MOD;
                dp[i][l] += rez;
                //dp[i+N][l] += rez;
                if(dp[i][l] >= MOD) dp[i][l] %= MOD;
            }
            //PRINT(i);
            //PRINT(l);
            //PRINT(dp[i][l]);
        }
    }
	return dp[1][N];
}