Символ \(\wedge\) довольно неоднозначный, особенно когда используется без контекста. Иногда используется для обозначения возведения в степень (\(a\wedge b = a^b\)), а иногда используется для обозначения операции побитового исключающего ИЛИ (\(a\wedge b=a\oplus b\)).
У вас неоднозначное выражение \(E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n\). Вы можете заменить каждый \(\wedge\) символ на \(\texttt{Power}\) (возведение в степень) или на \(\texttt{XOR}\) (исключающее ИЛИ), чтобы получить однозначное выражение \(E'\).
Значение выражения \(E'\) определяется по следующим правилам:
- Все \(\texttt{Power}\) операции выполняются перед всеми \(\texttt{XOR}\) операциями. Иными словами, \(\texttt{Power}\) операция имеет приоритет перед \(\texttt{XOR}\) операциями. Например, \(4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32\).
- Последовательные возведения в степень выполняются слева направо. Например, \(2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096\).
Вам дан массив \(B\) длины \(n\) и целое число \(k\). Массив \(A\) получается как \(A_i=2^{B_i}\) и выражение \(E\) получается как \(E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n\). Вам нужно найти XOR значений всех возможных однозначных выражений \(E'\), которые могут быть получены из \(E\) и имеют хотя бы \(k\) \(\wedge\) символов, используемых как \(\texttt{XOR}\) операции. Поскольку ответ может быть очень большим, вам нужно найти его по модулю \(2^{2^{20}}\). Поскольку это число также может быть очень большим, вам нужно вывести его двоичное представление без лидирующих нулей. Если ответ равен \(0\), выведите \(0\).
Выходные данные
Выведите единственную строку, содержащую двоичную строку без лидирующих нулей, обозначающую ответ на задачу. Если ответ равен \(0\), выведите \(0\).
Примечание
Для всех примеров с \(1\) до \(3\), \(A = \{2^3,2^1,2^2\} = \{8,2,4\}\) и \(E=8\wedge 2\wedge 4\).
В первом примере существует только одно возможное подходящее однозначное выражение \(E' = 8\oplus 2\oplus 4 = 14 = (1110)_2\).
Во втором примере существуют три возможные подходящие однозначные выражения \(E'\):
- \(8\oplus 2\oplus 4 = 14\)
- \(8^2\oplus 4 = 64\oplus 4= 68\)
- \(8\oplus 2^4 = 8\oplus 16= 24\)
XOR всех их значений равен
\(14\oplus 68\oplus 24 = 82 = (1010010)_2\).
Во третьем примере существуют четыре возможные подходящие однозначные выражения \(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 всех их значений равен
\(14\oplus 68\oplus 24\oplus 16777216 = 16777298 = (1000000000000000001010010)_2\).
В четвёртом примере \(A=\{2,2\}\) и \(E=2\wedge 2\). Единственное возможное подходящее однозначное выражение \(E' = 2\oplus 2 = 0 = (0)_2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
3 1 2
|
1110
|
|
2
|
3 1
3 1 2
|
1010010
|
|
3
|
3 0
3 1 2
|
1000000000000000001010010
|
|
4
|
2 1
1 1
|
0
|