题目描述

固定一个顶点数 $n$。本题中的所有图都是顶点编号为 $0,1,\ldots,n-1$ 的无向简单图。

对于若干张图组成的序列 $T$，定义 $\operatorname{XOR}(T)$：对于任意 $u<v$，当且仅当 $T$ 中包含边 $(u,v)$ 的图的数量为奇数时，$\operatorname{XOR}(T)$ 中存在边 $(u,v)$。

一张图用一个长度为 $n(n-1)/2$ 的 01 串表示。字符串中的边按以下顺序排列：先枚举 $u=0,1,\ldots,n-1$，再枚举 $v=u+1,u+2,\ldots,n-1$；字符为 1 表示存在边 $(u,v)$，否则为 0。

现在给定 $M$ 张图。你可以删除其中任意一些图（可以不删，也可以全部删除），剩余图按上述规则取异或。求有多少种删除下标集合，使最终异或图是连通图。

两种方案只要删除的图的下标集合不同，就视为不同方案。

输入格式

第一行一个整数 $M$。

接下来 $M$ 行，每行一个 01 串，表示一张图。所有字符串长度相同，并唯一确定 $n$。

输出格式

输出满足条件的删除方案数量。

数据范围

$1\le M\le50$；$2\le n\le9$；每个字符串长度恰为 $n(n-1)/2$。

样例

3
1
1
0

4