CF888F.Connecting Vertices

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.

平面上标有 $n$ 个点，这些点构成一个正 $n$ 边形（所标记的点即为其顶点，并按逆时针顺序编号）。你可以画出 $n-1$ 条线段，每条线段连接任意两个已标记的点，使得所有点彼此连通（直接或间接）。

但存在一些限制条件：
第一，某些点对之间不能直接相连，而必须通过其他点间接连通；
第二，你所画出的所有线段在除已标记点以外的任何位置均不得相交（即：若任意两条线段相交，且其交点不是某个已标记的点，则该图形无效）。

问：有多少种方式用 $n-1$ 条线段将所有顶点连通？若存在某一对点，在第一种连通方式中它们之间画有线段，而在第二种连通方式中没有，则认为这两种方式不同。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

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

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

第一行包含一个整数 $n$（$3 \leq n \leq 500$）—— 标记点的个数。

接下来有 $n$ 行，每行包含 $n$ 个元素。其中 $a_{i,j}$（第 $i$ 行的第 $j$ 个元素）等于 $1$ 当且仅当点 $i$ 和点 $j$ 可以直接相连（否则 $a_{i,j} = 0$）。保证对任意两点均有 $a_{i,j} = a_{j,i}$，且对任意点 $i$ 均有 $a_{i,i} = 0$。

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

输出连接点的方式数对 $10^9 + 7$ 取模的结果。