题目描述

定义两个结点数相同的图 $G_1$ 与图 $G_2$ 的异或为一个新的图 $G$，其中如果 $(u, v)$ 在 $G_1$ 与 $G_2$ 中的出现次数之和为 $1$，那么边 $(u, v)$ 在 $G$ 中，否则这条边不在 $G$ 中。

现在给定 $s$ 个结点数相同的图 $G_{1 \sim s}$， $S = \{G_1, G_2, \dots, G_s\}$，请问 $S$ 有多少个子集的异或为一个连通图？

输入格式

第一行为一个整数 $s$，表图的个数.

接下来每一个二进制串，第 $i$ 行的二进制串为 $g_i$，其中 $g_i$ 是原图通过以下伪代码转化得到的。图的结点从 $1$ 开始编号，下面设结点数为 $n$。

Algorithm 1 Print a graph G = (V, E)

for i = 1 to n do
for j = i + 1 to n do
if G contains edge (i, j) then
print 1
else
print 0
end if
end for
end for

输出格式

输出一行一个整数，表示方案数

输入输出样例

样例输入 #1

3 
1 
1 
0

样例输出 #1

4

数据范围与约定

对于 100% 的数据，$2 ≤ n ≤ 10$，$1 ≤ s ≤ 60$。