题目描述

在一个圆的周长上，共有$2N$个点，按照逆时针的顺序编号为$1,\\dots,2N$。如果对于其中的任意六个不同的点$U, V, W, X, Y,$和$Z$，线段$UV, WX,$和$YZ$没有交于同一点，则将这些点称为"generally positioned"。另外，给定一个$2N\\times 2N$的矩阵$A$。

找出满足以下条件的将$2N$个点分为$N$对的方法的数量：

• 对于每一对$(P, Q)$，有$A_{P,Q} = A_{Q,P} = 1$。

在每一对中，连接两个点的线段被涂红，这些红色线段组成一棵树。

例如，见下图：

• 左上：满足条件。
• 右上：红色线段形成循环，因此不满足条件。
• 左下：红色线段不连通，因此不满足条件。
• 右下：某些顶点不属于任何一对或属于多对，因此不满足条件。

图示：满足条件的分割（左上）和不满足条件的分割（其余部分）

注意事项

可以证明，只要$2N$个点是"generally positioned"，答案不依赖于它们的具体位置。

约束条件

• $1 \\leq N \\leq 20$
• $A_{i,j}$为0或1。
• $A_{i,i}$为0。
• $A_{i,j}=A_{j,i}$
• $N$为整数。

输入

输入通过标准输入给出，格式如下：

$N$ $A_{1,1}...A_{1,2N}$ $:$ $A_{2N,1}...A_{2N,2N}$

输出

打印出满足条件的将$2N$个点分为$N$对的方法的数量。可以证明，在给定的约束条件下，答案可以用64位有符号整数表示。

示例输入 1

3
011111
101111
110111
111011
111101
111110

示例输出 1

3

有三种满足条件的分割方式：$((1,4),(2,6),(3,5))$，$((1,3),(2,5),(4,6))$，$((1,5),(2,4),(3,6))$。

示例输入 2

4
01111100
10011111
10011100
11101111
11110111
11111011
01011101
01011110

示例输出 2

6

示例输入 3

8
0111101111111111
1011101111111111
1101101111011101
1110111111111111
1111011111110111
0001101111111111
1111110111011111
1111111011111111
1111111101111111
1111111110111111
1101110111011111
1111111111101111
1111011111110111
1111111111111011
1101111111111101
1111111111111110

示例输出 3

4762