平面上标记有 n 个点。这些点的位置使得它们形成正多边形(标记的点是其顶点,并且它们按逆时针顺序编号)。您可以绘制 n - 1 条线段,每条线段连接任意两个标记点,这样所有点都必须相互连接(直接或间接)。
但有一些限制。首先,有些点对不能直接连接,必须间接连接。其次,你画的线段不能在标记点以外的任何点相交(也就是说,如果任意两条线段相交,并且它们的交点不是标记点,那么你画的图就是无效的)。
有多少种方法可以用 n - 1 条线段连接所有顶点?两种方式被认为是不同的,如果存在一对点,使得在第一种连接方式中在它们之间绘制线段,但在第二种连接方式中不在这些点之间绘制线段。由于答案可能很大,因此输出它对 109 + 7 求模。
输入
第一行包含一个数字 n (3 ≤ n ≤ 500) — 标记点的数量。
接下来是 n 行,每行包含 n 个元素。 ai, j(第 i 行的第 j 个元素)等于 1,当且仅当您可以直接连接点 i 和 j(否则 ai, j = 0)。保证对于任何一对点 ai,j = aj, i,并且对于任何点 ai,i = 0。
输出
打印以 109 + 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