CF1673E.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 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$ .

For each of the testcases $1$ to $3$ , $A = \{2^3,2^1,2^2\} = \{8,2,4\}$ and $E=8\wedge 2\wedge 4$ .

For the first testcase, there is only one possible valid unambiguous expression $E' = 8\oplus 2\oplus 4 = 14 = (1110)_2$ .

For the second testcase, there are three possible valid unambiguous expressions $E'$ :

• $8\oplus 2\oplus 4 = 14$
• $8^2\oplus 4 = 64\oplus 4= 68$
• $8\oplus 2^4 = 8\oplus 16= 24$

XOR of the values of all of these is $14\oplus 68\oplus 24 = 82 = (1010010)_2$ .For the third testcase, there are four possible valid unambiguous expressions $E'$ :

• $8\oplus 2\oplus 4 = 14$
• $8^2\oplus 4 = 64\oplus 4= 68$
• $8\oplus 2^4 = 8\oplus 16= 24$
• $(8^2)^4 = 64^4 = 2^{24} = 16777216$

XOR of the values of all of these is $14\oplus 68\oplus 24\oplus 16777216 = 16777298 = (1000000000000000001010010)_2$ .For the fourth testcase, $A=\{2,2\}$ and $E=2\wedge 2$ . The only possible valid unambiguous expression $E' = 2\oplus 2 = 0 = (0)_2$ .