A14988 | Power or XOR?

The symbol $\wedge$ is quite ambiguous, especially when used without context. Sometimes it is used to denote a power ( $a\wedge b = a^b$ ) and sometimes it is used to denote the [XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) operation ( $a\wedge b=a\oplus b$ ).

You have an ambiguous expression $E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$ . You can replace each $\wedge$ symbol with either a $\texttt{Power}$ operation or a $\texttt{XOR}$ operation to get an unambiguous expression $E'$ .

The value of this expression $E'$ is determined according to the following rules:

- All $\texttt{Power}$ operations are performed before any $\texttt{XOR}$ operation. In other words, the $\texttt{Power}$ operation takes precedence over $\texttt{XOR}$ operation. For example, $4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32$ .
- Consecutive powers are calculated from left to right. For example, $2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096$ .

You are given an array $B$ of length $n$ and an integer $k$ . The array $A$ is given by $A_i=2^{B_i}$ and the expression $E$ is given by $E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$ . You need to find the XOR of the values of all possible unambiguous expressions $E'$ which can be obtained from $E$ and has at least $k$ $\wedge$ symbols used as $\texttt{XOR}$ operation. Since the answer can be very large, you need to find it modulo $2^{2^{20}}$ . Since this number can also be very large, you need to print its binary representation without leading zeroes. If the answer is equal to $0$ , print $0$ .

The first line of input contains two integers $n$ and $k$ $(1\leq n\leq 2^{20}, 0\leq k < n)$ .

The second line of input contains $n$ integers $B_1,B_2,\ldots,B_n$ $(1\leq B_i < 2^{20})$ .

Print a single line containing a binary string without leading zeroes denoting the answer to the problem. If the answer is equal to $0$ , print $0$ .