#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &x) {
  return os << "(" << x.first << "," << x.second << ")";
}
namespace dbg_ns {
template <typename C>
struct is_iterable {
  template <class T>
  static long check(...);
  template <class T>
  static char check(int, typename T::const_iterator = C().end());
  enum {
    value = sizeof(check<C>(0)) == sizeof(char),
    neg_value = sizeof(check<C>(0)) != sizeof(char)
  };
};
template <class T>
ostream &_out_str(ostream &os, const T &x) {
  return os << '"' << x << '"';
}
template <class T>
ostream &_dbg2_5(ostream &, const T &);
template <bool B, typename T = void>
using eit = typename enable_if<B, T>::type;
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::neg_value, const T> &x) {
  return os << x;
}
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::value, const T> &V) {
  os << "{";
  bool ff = 0;
  for (const auto &E : V) _dbg2_5(ff ? os << "," : os, E), ff = 1;
  return os << "}";
}
template <>
inline ostream &_dbg3<string>(ostream &os, const string &x) {
  return _out_str(os, x);
}
template <>
inline ostream &_dbg3<const char *>(ostream &os, const char *const &x) {
  return _out_str(os, x);
}
template <class T>
inline ostream &_dbg2_5(ostream &os, const T &x) {
  return _dbg3<T>(os, x);
}
template <class T, typename... Args>
ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
               Args &&...args);
inline ostream &_dbg2(ostream &os, vector<string>::iterator) { return os; }
template <typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const char *x,
                      Args &&...args) {
  return _dbg2(_dbg3<const char *>(os << "  ", x), nm + 1, args...);
}
template <class T, typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
                      Args &&...args) {
  return _dbg2(_dbg3<T>(os << "  " << *nm << "=", x), nm + 1, args...);
}
vector<string> split(string s) {
  vector<string> Z;
  string z = "";
  s += ',';
  int dep = 0;
  for (char c : s) {
    if (c == ',' && !dep)
      Z.push_back(z), z = "";
    else
      z += c;
    if (c == '(') ++dep;
    if (c == ')') --dep;
  }
  return Z;
}
template <typename... Args>
inline ostream &_dbg1(int ln, const string &nm, Args &&...args) {
  auto nms = split(nm);
  return _dbg2(cerr << "L" << ln << ":", nms.begin(), args...) << endl;
}
}  // namespace dbg_ns
typedef long double ld;
const ld eps = (ld)1e-8;
const ld tau = 2 * (ld)acosl(-1);
const int inf = 1e9 + 99;
const long long linf = 1e18 + 99;
const int P = 1e9 + 7;
void add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
const int N = 512;
int n, a[N][N];
int solve_half(int, int);
int solve_full(int L, int R) {
  static int dp[N][N];
  static bool seen[N][N];
  int &ans = dp[L][R];
  bool &sn = seen[L][R];
  if (sn) return ans;
  sn = 1;
  if (L + 1 == R) return ans = 1;
  ans = solve_half(L, R - 1);
  for (int M = L + 1; M <= R - 1; M++) {
    if (!a[M][R]) continue;
    add(ans, int(1LL * solve_full(L, M) * solve_full(M, R) % P));
  }
  return ans;
}
int solve_half(int L, int R) {
  static int dp[N][N];
  static bool seen[N][N];
  int &ans = dp[L][R];
  bool &sn = seen[L][R];
  if (sn) return ans;
  sn = 1;
  if (L == R) return ans = 1;
  ans = 0;
  for (int M = L + 1; M <= R; M++) {
    if (!a[L][M]) continue;
    add(ans, int(1LL * solve_full(L, M) * solve_half(M, R) % P));
  }
  return ans;
}
int32_t main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
  printf("%d\n", solve_half(1, n));
}

### Prompt

Construct a Cpp code solution to the problem outlined:

There are n points marked on the plane. The points are situated in such a way that they form a regular polygon (marked points are its vertices, and they are numbered in counter-clockwise order). You can draw n - 1 segments, each connecting any two marked points, in such a way that all points have to be connected with each other (directly or indirectly).

But there are some restrictions. Firstly, some pairs of points cannot be connected directly and have to be connected undirectly. Secondly, the segments you draw must not intersect in any point apart from the marked points (that is, if any two segments intersect and their intersection is not a marked point, then the picture you have drawn is invalid).

How many ways are there to connect all vertices with n - 1 segments? Two ways are considered different iff there exist some pair of points such that a segment is drawn between them in the first way of connection, but it is not drawn between these points in the second one. Since the answer might be large, output it modulo 109 + 7.

Input

The first line contains one number n (3 ≤ n ≤ 500) — the number of marked points.

Then n lines follow, each containing n elements. ai, j (j-th element of line i) is equal to 1 iff you can connect points i and j directly (otherwise ai, j = 0). It is guaranteed that for any pair of points ai, j = aj, i, and for any point ai, i = 0.

Output

Print the number of ways to connect points modulo 109 + 7.

Examples

Input

3
0 0 1
0 0 1
1 1 0


Output

1


Input

4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0


Output

12


Input

3
0 0 0
0 0 1
0 1 0


Output

0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &x) {
  return os << "(" << x.first << "," << x.second << ")";
}
namespace dbg_ns {
template <typename C>
struct is_iterable {
  template <class T>
  static long check(...);
  template <class T>
  static char check(int, typename T::const_iterator = C().end());
  enum {
    value = sizeof(check<C>(0)) == sizeof(char),
    neg_value = sizeof(check<C>(0)) != sizeof(char)
  };
};
template <class T>
ostream &_out_str(ostream &os, const T &x) {
  return os << '"' << x << '"';
}
template <class T>
ostream &_dbg2_5(ostream &, const T &);
template <bool B, typename T = void>
using eit = typename enable_if<B, T>::type;
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::neg_value, const T> &x) {
  return os << x;
}
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::value, const T> &V) {
  os << "{";
  bool ff = 0;
  for (const auto &E : V) _dbg2_5(ff ? os << "," : os, E), ff = 1;
  return os << "}";
}
template <>
inline ostream &_dbg3<string>(ostream &os, const string &x) {
  return _out_str(os, x);
}
template <>
inline ostream &_dbg3<const char *>(ostream &os, const char *const &x) {
  return _out_str(os, x);
}
template <class T>
inline ostream &_dbg2_5(ostream &os, const T &x) {
  return _dbg3<T>(os, x);
}
template <class T, typename... Args>
ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
               Args &&...args);
inline ostream &_dbg2(ostream &os, vector<string>::iterator) { return os; }
template <typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const char *x,
                      Args &&...args) {
  return _dbg2(_dbg3<const char *>(os << "  ", x), nm + 1, args...);
}
template <class T, typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
                      Args &&...args) {
  return _dbg2(_dbg3<T>(os << "  " << *nm << "=", x), nm + 1, args...);
}
vector<string> split(string s) {
  vector<string> Z;
  string z = "";
  s += ',';
  int dep = 0;
  for (char c : s) {
    if (c == ',' && !dep)
      Z.push_back(z), z = "";
    else
      z += c;
    if (c == '(') ++dep;
    if (c == ')') --dep;
  }
  return Z;
}
template <typename... Args>
inline ostream &_dbg1(int ln, const string &nm, Args &&...args) {
  auto nms = split(nm);
  return _dbg2(cerr << "L" << ln << ":", nms.begin(), args...) << endl;
}
}  // namespace dbg_ns
typedef long double ld;
const ld eps = (ld)1e-8;
const ld tau = 2 * (ld)acosl(-1);
const int inf = 1e9 + 99;
const long long linf = 1e18 + 99;
const int P = 1e9 + 7;
void add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
const int N = 512;
int n, a[N][N];
int solve_half(int, int);
int solve_full(int L, int R) {
  static int dp[N][N];
  static bool seen[N][N];
  int &ans = dp[L][R];
  bool &sn = seen[L][R];
  if (sn) return ans;
  sn = 1;
  if (L + 1 == R) return ans = 1;
  ans = solve_half(L, R - 1);
  for (int M = L + 1; M <= R - 1; M++) {
    if (!a[M][R]) continue;
    add(ans, int(1LL * solve_full(L, M) * solve_full(M, R) % P));
  }
  return ans;
}
int solve_half(int L, int R) {
  static int dp[N][N];
  static bool seen[N][N];
  int &ans = dp[L][R];
  bool &sn = seen[L][R];
  if (sn) return ans;
  sn = 1;
  if (L == R) return ans = 1;
  ans = 0;
  for (int M = L + 1; M <= R; M++) {
    if (!a[L][M]) continue;
    add(ans, int(1LL * solve_full(L, M) * solve_half(M, R) % P));
  }
  return ans;
}
int32_t main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
  printf("%d\n", solve_half(1, n));
}

```