#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];
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));
}
int translate(int K) {
    while(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;
    for(int i = 1; i <= N; i++) {
        a[i] = A[i];
    }
    n = N;
    for(int l = 4; l <= N; l+=4) {
        for(int i = 1; i <= N; i++) {
            for(int i1 = 0; i1 < l; i1 += 4) {
                for(int i2 = 0; i2 < l-i1-2; i2++) {
                    int idx1 = i;
                    int idx2 = translate(i+i1+1);
                    int idx3 = translate(i+i1+i2+2);
                    int idx4 = translate(i+l-1);
                    if(valid(idx1, idx2, idx3, idx4)) {
                        lld rez = dp[translate(idx1+1)][i1]*dp[translate(idx2+1)][i2];
                        if(rez >= MOD) rez %= MOD;
                        rez *= dp[translate(idx3+1)][l-4-i1-i2];
                        if(rez >= MOD) rez %= MOD;
                        dp1[i][l] += rez;
                        if(dp1[i][l] >= MOD) dp1[i][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;
            }
            //PRINT(i);
            //PRINT(l);
            //PRINT(dp[i][l]);
        }
    }
    lld rez = 0;
    /*for(int i = 1; i <= N; i++) {
        for(int i1 = 0; i1 < N; i1 += 4) {
            for(int i2 = 0; i2 < N-i1-1; i2 += 4) {
                for(int i3 = 0; i3 < N-i1-i2-2; i3 += 4) {
                    int idx1 = translate(i+i1+1);
                    int idx2 = translate(i+i1+i2+2);
                    int idx3 = translate(i+i1+i2+i3+3);
                    if(a[idx1]!= a[i] && a[idx2] != a[i] && a[idx3] != a[i]) {
                        //PRINT("koliko");
                                                //PRINT(i);
//PRINT(idx1);
                        //PRINT(idx2);
                        //PRINT(idx3);
                        lld tmp = dp[translate(i+1)][i1] * dp[translate(idx1+1)][i2];
                        if(tmp >= MOD) tmp %= MOD;
                        tmp *= dp[translate(idx2+1)][i3];
                        if(tmp >= MOD) tmp %= MOD;
                        tmp *= dp[translate(idx3+1)][N-4-i1-i2-i3];
                        if(tmp >= MOD) tmp %= MOD;
                        rez += tmp;
                        if(rez >= MOD) rez %= MOD;
                    }
                }
            }
        }
    }*/
	return dp[1][N];
}