Home

Contest: Task: Related: TaskD TaskF

Score : $1500$ points

Problem Statement

There are $2N$ points generally positioned on the circumference of a circle, numbered $1,\dots,2N$ in counterclockwise order. Here, a set of points is said to be generally positioned if, for any six distinct points $U, V, W, X, Y,$ and $Z$ among them, the segments $UV, WX,$ and $YZ$ do not intersect at the same point. Additionally, you will be given a $2N\times 2N$ matrix $A$.

Find the number of ways to divide the $2N$ points into $N$ pairs such that all of the following are satisfied:

  • Let us draw a red segment connecting the two points for each pair. Then, those red segments form a tree.
  • For each pair $(P, Q)$, $A_{P,Q} = A_{Q,P} = 1$ holds.

Here, a set of segments is said to form a tree if they are all connected and form no cycles.

For example, see the figure below:

  • Upper left: the conditions are satisfied.
  • Upper right: the red segments form a cycle, so the conditions are not satisfied.
  • Lower left: the red segments are not connected, so the conditions are not satisfied.
  • Lower right: some vertices belong to no pair or multiple pairs, so the conditions are not satisfied.

Figure: A division satisfying the conditions (upper left) and divisions violating them (the others)

Notes

It can be proved that, as long as the $2N$ points are generally positioned, the answer does not depend on their specific positions.

Constraints

  • $1 \leq N \leq 20$
  • $A_{i,j}$ is 0 or 1.
  • $A_{i,i}$ is 0.
  • $A_{i,j}=A_{j,i}$
  • $N$ is an integer.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of ways to divide the $2N$ points into $N$ pairs such that all of the conditions are satisfied. It can be proved that the answer fits into a $64$-bit signed integer under the given constraints.

Sample Input 1

3
011111
101111
110111
111011
111101
111110

Sample Output 1

3

There are three possible divisions that satisfy the conditions: $((1,4),(2,6),(3,5))$, $((1,3),(2,5),(4,6))$, and $((1,5),(2,4),(3,6))$.

Sample Input 2

4
01111100
10011111
10011100
11101111
11110111
11111011
01011101
01011110

Sample Output 2

6

Sample Input 3

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

Sample Output 3

4762