407697: GYM102875 K Kanade Hates Recruitment

Because of the thriller adventure game The 3rd Building, more and more students get interested in workshops. Because of this, Kanade found that when the recruitment just started, many more students participated this year than before. But Kanade hates recruitment. She is annoyed by preparing recruitment questions. It's time for her to set a question, but she has no idea.

One day, she came up with an idea. Given $$$n$$$ binary strings, i.e., strings only consist of 0 and 1. Now she'd like to choose $$$\textbf{one}$$$ binary string among them, then spilt it into two non-empty binary strings. Formally, for binary string $$$s_i$$$ whose length is $$$l\ (l\ge 2)$$$, she will choose an integer $$$k\in[1,l-1]$$$ at first. Then let the prefix of $$$s_i$$$ of length $$$k$$$ be a new binary string $$$s_{n+1}$$$. Finally, delete that prefix from string $$$s_i$$$. After this operation, the length of $$$s_i$$$ becomes $$$l-k$$$, and there are $$$n+1$$$ binary strings.

Kanade wants to know the number of different operations which can make the exclusive-or of the $$$n+1$$$ binary strings only contains 0. Two operations consider different if the binary strings which are chosen to split are different, or the values of $$$k$$$ are different.

Let $$$a$$$ be a binary string whose length is $$$n$$$, $$$b$$$ be a binary string whose length is $$$m$$$. Let $$$c$$$ be the exclusive-or of $$$a$$$ and $$$b$$$, denoted $$$a \oplus b$$$, then $$$c$$$ is a binary string of length $$$\max\{n, m\}$$$, which is defined as

$$$$$$ c_i= (a \oplus b)_i = \begin{cases} \texttt{1}, & (1\le i\le \min\{n,m\},a_i\neq b_i)\\ \texttt{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} $$$$$$

The exclusive-or of $$$n+1$$$ strings $$$s_1, s_2, \cdots, s_n, s_{n+1}$$$ is thus defined as $$$s_1 \oplus s_2 \oplus \cdots \oplus s_n \oplus s_{n+1}$$$.

Note that a binary string is a string where each character is indexed from left to right. This is different from the binary form of an integer.

She thought it easy to solve, but few students managed this question. She wants to know if her standard program was wrong. Please write a program solving the question above, so that she can check her code.

The first line contains an integer $$$n\ (1\le n\le 10^5)$$$ — the number of binary strings.

In the next $$$n$$$ lines, each line contains a binary string $$$s_i\ (1\le |s_i|\le 10^6)$$$, where $$$|s_i|$$$ denotes the length of $$$s_i$$$. The sum of all binary strings' lengths will not exceed $$$10^6$$$.

It is guaranteed that there exists a binary string whose length is greater than $$$1$$$.

Output one integer in a line, representing the answer.

4
001
010
011
101

4