Connecting Vertices

题意翻译

有一个正 $N$ 边形，顶点顺时针编号为 $1\sim N$。问用 $N - 1$ 条线段连接这 $N$ 个顶点，使它们连成一棵树，有多少种方法。 连边时有以下限制： - 给出一个 $N \times N$ 的 $01$ 矩阵 $A$，$A_{i,j}= 1$ 表示顶点 $i$ 和顶点 $j$ 可以直接相连，而 $A_{i,j}=0$ 时则不能。保证了 $A_{i,i}= 0$，$A_{i,j}=A_{j,i}$。 - 两条线段不能在顶点之外的地方相交，如不能同时连 $(1,3)$ 和 $(2,4)$。

题目描述

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 $ 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 $ .

输出格式

Print the number of ways to connect points modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

3
0 0 1
0 0 1
1 1 0

输出样例 #1

1

输入样例 #2

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

输出样例 #2

12

输入样例 #3

3
0 0 0
0 0 1
0 1 0

输出样例 #3

0