#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define MAXN 505

const int MOD =1e9+7;

using namespace std;
int dp[MAXN][MAXN];
int Zvezda(int n, int *a){
    a[0]=a[n];
    for(int i=1;i<n;i++)dp[i][i-1]=1;
    dp[0][n-1]=1;

    for(int v=3;v<n;v+=4){
        for(int i=0;i<n;i++){
            int j=(i+v)%n;

            for(int k=3;k<v;k+=4){
                int kj=(i+k)%n;
                dp[i][j]=(dp[i][j]+dp[i][kj]*dp[(kj+1)%n][j])%MOD;
            }

            if(a[i]!=a[j])continue;
            for(int x=i+1;(x!=j-1 && x!=n+j-1);x++){
                for(int y=x+1;(y!=j && y!=j+n); y++){
                    int px=(x)%n;
                    int py=(y)%n;

                    if(a[px]==a[py])continue;
                    //printf("  %d %d  %d %d    %d %d\n",i,x,y,j,(n+px-1)%n,(n+py-1)%n);
                    dp[i][j]=(dp[i][j]+  ((dp[(i+1)%n][(n+px-1)%n]*dp[(px+1)%n][(n+py-1)%n])%MOD)*dp[(py+1)%n][(n+j-1)%n]   )%MOD;
                }
            }

        }
    }

    int res=dp[0][n-1];
    for(int i=1;i<n;i++)res=max(res,dp[i-1][i]);


    //printf("%d\n",dp[1][4]);
    return res;
}