XOR Transition Equality

Given \(n+1\) integers \(a_0, a_1, \dots, a_n\), define a function \(f(u)\) for a non-negative integer \(u\) as follows. Write \(u\) in binary; let the positions (numbered from right to left starting at \(0\)) of the bits equal to \(1\) be \(k_1, k_2, \dots, k_m\). Then

\[ f(u)=a_{k_1}\oplus a_{k_2}\oplus\cdots\oplus a_{k_m}, \]

where \(\oplus\) denotes the bitwise XOR operation.

You need to count the number of integers \(u\) with \(0\le u\le 2^n-1\) satisfying \(f(u)=f(u+1)\). Notice that when \(u=2^n-1\), the number \(u+1\) has its binary representation with a single \(1\) in the \(n\)th bit, so the value \(a_n\) is used in computing \(f(u+1)\). In other words, even though \(u\) is at most \(2^n-1\), the definition of \(f(\cdot)\) involves the array indices \(0,1,\dots,n\>.

It can be shown that if \(u\) ends with exactly \(t\) consecutive ones (with \(0\le t\le n\)), then the equality \(f(u)=f(u+1)\) holds if and only if

\[ a_t=\bigoplus_{i=0}^{t-1}a_i, \]

For each \(t\) satisfying the above condition, the number of \(u\) with exactly \(t\) trailing ones is:

• For \(0\le t<n\): \(2^{n-t-1}\)
• For \(t=n\): \(1\) (this corresponds to \(u=2^n-1\))

Your task is to sum these counts over all \(t=0,1,\dots,n\) for which \(a_t=\bigoplus_{i=0}^{t-1}a_i\) holds, and then output the total count in its binary representation without leading zeros (unless the answer is 0).

inputFormat

The first line contains a single integer \(n\) (\(1\le n\le 60\)).

The second line contains \(n+1\) space-separated integers: \(a_0, a_1, \dots, a_n\).

outputFormat

Output a binary string representing the count of integers \(0\le u\le 2^n-1\) satisfying \(f(u)=f(u+1)\). The binary representation should not contain any leading zeros (unless the answer is 0).

sample

1
0 0

10