You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

平面上标有 $n$ 个点。这些点以规则（正）多边形的形式排列（标记的点是其顶点，按逆时针编号）。你可以画出 $n-1$ 条线段，每条线段连接任意两个标记的点，要求所有点必须直接或间接连接。

但是有一些限制。首先，某些点对之间不能直接连接，必须间接连接。其次，你画出的线段除了在已标记的点上不能有其它交点（也就是说，如果任意两条线段的交点不是标记的点，则构图不合法）。

有多少种方式可以用 $n-1$ 条线段将所有顶点连接起来？当且仅当存在某一对点，在第一种连接方式画有它们之间的线段，在第二种连接方式却没有（或反之），这两种方式才被认为是不同的。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

输入格式

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

接下来的 $n$ 行，每行有 $n$ 个元素。当且仅当你可以直接连接点 $i$ 和点 $j$ 时，第 $i$ 行第 $j$ 个元素 $a_{i, j}=1$（否则 $a_{i, j}=0$）。保证对于任意的点对有 $a_{i, j}=a_{j, i}$，并且任意点 $a_{i, i}=0$。

输出格式

输出将所有点连接的方式数，对 $10^9+7$ 取模。

3
0 0 1
0 0 1
1 1 0

1

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

12

3
0 0 0
0 0 1
0 1 0

0