When you fell, earth wrote patterns on your coat These stains my badge, proof I’m still afloat

MiserableMagical 凝望着星空，并将所有星星的信息输入到一个软件中。星空可以看作一个二维平面，每颗星星都有唯一的 $x$ 和 $y$ 坐标。第 $i$ 颗星星的坐标为 $(i, p_i)$，其中 $p_i$ 是 $1$ 到 $n$ 的一个排列。软件会根据星星的信息自动生成一张“星图”。如果两颗星星中，一颗在另一颗的右上方，且它们构成的矩形内没有其他星星，则这两颗星星之间会用一条亮线连接。换句话说，星星 $i$ 和 $j$ 相连当且仅当 $i < j$ 且 $p_i < p_j$，并且不存在 $k$ 满足 $i < k < j$ 且 $p_i < p_k < p_j$。

这里是“星图”的一个示意图：

有一次，MiserableMagical 的软件崩溃了，当他重新打开它时，所有的信息都丢失了。他只记得星图没有环，并且某些星星对之间没有相连。你需要计算所有可能的“星空”的数量。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 20$)，表示星星的数量。

接下来的 $n$ 行，每行包含 $n$ 个整数 $a_{i,j}$ ($a_{i,j} \in \{0, 1\}$)。如果 $a_{i,j} = 0$，表示星星 $i$ 和 $j$ 没有相连。如果 $a_{i,j} = 1$，表示星星 $i$ 和 $j$ 可能相连，也可能不相连。保证 $a_{i,i} = 0$ 且 $a_{i,j} = a_{j,i}$。

输出格式

输出一个整数，表示所有可能的“星空”的数量。注意，本题不需要取模。

样例

输入样例 1

3
0 1 1
1 0 0
1 0 0

输出样例 1

3

输入样例 2

5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

输出样例 2

89

说明

在第一个样例中，有 3 种可能的“星空”，如下图所示：