时间限制： 1.0 秒

空间限制： 512 MB

题目描述

有 $n$ 个选手在打擂台赛，编号为 $1$ 到 $n$，保证 $n$ 是 $2$ 的幂次且 $n\le 8$。

一开始会将 $n$ 个选手分成 $n/2$ 组，每组 $2$ 个选手。组内比赛之后胜出者进入下一轮，直到剩下最后一位选手为最终的胜者。

当 $n=4$ 时，先将 $4$ 个选手分成 $2$ 组，第一组的胜者和第二组的胜者进行最后的比赛。

当 $n=8$ 时，先将 $8$ 个选手分成 $4$ 组，第一组的胜者和第二组的胜者进行下一轮的比赛，第三组的胜者和第四组的胜者进行下一轮的比赛，两边的胜者再进行最后的比赛。

给出 $n$ 个选手之间互相比赛的胜负情况，问有多少组的方案使得最后编号为 $1$ 的选手胜出。两种方案被认为是不同的，当且仅当两种方案存在至少一位选手分到的组的编号不同。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示参加擂台赛的人数。

接下来 $n$ 行，每行 $n$ 个数字。其中第 $i$ 行，第 $j$ 个数字 $a_{i,j}$ 表示编号为 $i$ 的选手和编号为 $j$ 的选手比赛的胜负情况，$a_{i,j}=1$ 表示编号为 $i$ 的选手胜出，$a_{i,j}=-1$ 表示编号为 $j$ 的选手胜出。当 $i=j$ 时， $a_{i,j}=0$。

输出格式

输出到标准输出。

输出一行包含一个非负整数表示对应的方案数。

4
0 1 1 1
-1 0 1 1
-1 -1 0 1
-1 -1 -1 0

6

样例 1 解释

一共有六种方案，以下是对应分组的情况：

• (1,2) (3,4)
• (1,3) (2,4)
• (1,4) (2,3)
• (3,4) (1,2)
• (2,4) (1,3)
• (2,3) (1,4)

数据范围

对于所有测试数据，满足 $2\le n\le 8,~-1\le a_{i,j}\le 1$，$a_{i,j}$ 构成的矩阵一定为一个对角线元素为 $0$，其他元素非 $0$ 的反对称矩阵（即 $a_{i,j}+a_{j,i}=0$）。

子任务 1（20 分）：满足 $n=2$。

子任务 2（40 分）：满足 $n=4$。

子任务 3（40 分）：满足 $n=8$。