因为惊悚冒险游戏《The 3rd Building》的缘故，越来越多的学生对研讨会产生了兴趣。正因如此，Kanade 发现今年招新刚开始时，参与的学生比往年多了许多。但 Kanade 讨厌招新。她对准备招新题目感到厌烦。现在是她出题的时候了，但她毫无头绪。

有一天，她想到了一个主意。给定 $n$ 个二进制字符串，即仅由 0 和 1 组成的字符串。现在她想从中选择一个二进制字符串，然后将其拆分为两个非空的二进制字符串。形式化地，对于长度为 $l$ ($l \ge 2$) 的二进制字符串 $s_i$，她首先选择一个整数 $k \in [1, l - 1]$。然后，令 $s_i$ 的长度为 $k$ 的前缀作为新的二进制字符串 $s_{n+1}$。最后，从字符串 $s_i$ 中删除该前缀。经过此操作后，$s_i$ 的长度变为 $l - k$，此时共有 $n + 1$ 个二进制字符串。

Kanade 想知道有多少种不同的操作，使得这 $n + 1$ 个二进制字符串的异或结果仅包含 0。如果选择拆分的二进制字符串不同，或者 $k$ 的值不同，则认为两次操作不同。

设 $a$ 为长度为 $n$ 的二进制字符串，$b$ 为长度为 $m$ 的二进制字符串。设 $c$ 为 $a$ 和 $b$ 的异或，记作 $a \oplus b$，则 $c$ 是一个长度为 $\max\{n, m\}$ 的二进制字符串，定义如下：

$$ c_i = (a \oplus b)_i = \begin{cases} 1, & (1 \le i \le \min\{n, m\}, a_i \neq b_i) \\ 0, & (1 \le i \le \min\{n, m\}, a_i = b_i) \\ a_i, & (i > \min\{n, m\}, n > m) \\ b_i, & (i > \min\{n, m\}, n < m) \end{cases} $$

因此，$n + 1$ 个字符串 $s_1, s_2, \dots, s_n, s_{n+1}$ 的异或定义为 $s_1 \oplus s_2 \oplus \dots \oplus s_n \oplus s_{n+1}$。

注意，二进制字符串是指从左到右索引字符的字符串。这与整数的二进制形式不同。

她认为这道题很容易解决，但很少有学生能做出来。她想知道她的标准程序是否出错了。请编写一个程序来解决上述问题，以便她检查自己的代码。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示二进制字符串的数量。

接下来的 $n$ 行，每行包含一个二进制字符串 $s_i$ ($1 \le |s_i| \le 10^6$)，其中 $|s_i|$ 表示 $s_i$ 的长度。所有二进制字符串的长度之和不超过 $10^6$。

保证存在至少一个长度大于 1 的二进制字符串。

输出格式

输出一行一个整数，表示答案。

样例

输入 1

4
001
010
011
101

输出 1

4