#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[2*MAXN][MAXN]; ///pocetak, duzina, sa pocetka do kraja
lld dp[2*MAXN][MAXN]; ///pocetak, duzina, kako god
bool a[MAXN];
int n;
inline int translate(int K) {
    if(K > n) K -= n;
    return K;
}
int Zvezda(int N, int* A) {
    for(int i = 1; i <= N; i++) dp[i][0] = dp1[i][0] = dp[i+N][0] = dp1[i+N][0] = 1, a[i] = a[i+N] = A[i];

    n = N;
    for(int l = 4; l <= N; l+=4) {
        for(int i = 1; i <= N; i++) {
            int d = i+l-1;
            if(a[i] != a[d]) {
                for(int i1 = 0; i1 < l; i1 += 4) {
                    lld sum = 0;
                    int gr = l-i1-2;
                    for(int i2 = 0; i2 < gr; i2 += 4) {
                        int idx2 = i+i1+1;
                        int idx3 = idx2+i2+1;
                        if(a[idx2] == a[idx3]) {
                            sum += dp[idx3+1][l-4-i1-i2]*dp[idx2+1][i2];
                            if(sum >= LINF) sum %= MOD;
                        }
                    }
                    if(sum >= MOD) sum %= MOD;
                    dp1[i][l] += sum*dp[i+1][i1];
                    if(dp1[i][l] >= LINF) dp1[i][l] %= MOD;
                }
            } else {
                for(int i1 = 0; i1 < l; i1 += 4) {
                    lld sum = 0;
                    int gr = l-i1-2;
                    for(int i2 = 0; i2 < gr; i2 += 4) {
                        int idx2 = i+i1+1;
                        int idx3 = idx2+i2+1;
                        if(a[idx2] != a[idx3]) {
                            sum += dp[idx3+1][l-4-i1-i2]*dp[idx2+1][i2];
                            if(sum >= LINF) sum %= MOD;
                        }
                    }
                    if(sum >= MOD) sum %= MOD;
                    dp1[i][l] += sum*dp[i+1][i1];
                    if(dp1[i][l] >= LINF) dp1[i][l] %= MOD;
                }
            }
            if(dp1[i][l] >= MOD) dp1[i][l] %= MOD;
            dp1[i+N][l] = dp1[i][l];
            for(int i1 = 4; i1 <= l; i1 += 4) {
                dp[i][l] += dp1[i][i1]*dp[i+i1][l-i1];
                if(dp[i][l] >= LINF) dp[i][l] %= MOD;
            }
            if(dp[i][l] >= MOD) dp[i][l] %= MOD;
            dp[i+N][l] = dp[i][l];
        }
    }
	return dp[1][N];
}