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)
## 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}$
[samples]
## Notes
It can be proved that, as long as the $2N$ points are generally positioned, the answer does not depend on their specific positions.