Дано число $$$k$$$. Есть последовательность $$$n$$$-битных бинарных чисел $$$a_1, a_2, \ldots, a_{2^k + 1}$$$. Числа $$$a_1$$$ и $$$a_{2^k + 1}$$$ вам даны, а остальные неизвестны. После этого неизвестные числа заполняются следующим образом за $$$k$$$ шагов:

• Пусть перед $$$i$$$-м шагом были заполнены числа с номерами $$$p_1 \lt p_2 \lt \ldots \lt p_m$$$. (Перед первым шагом это числа с номерами $$$1, 2^{k} + 1$$$).
• Затем для каждого $$$j$$$ от $$$1$$$ до $$$m - 1$$$ выполняется $$$a_{\frac{p_j + p_{j + 1}}{2}} := a_{p_j} \oplus a_{p_{j + 1}}$$$$$$^{\text{∗}}$$$.
• Эти присвоения происходят одновременно, а после все эти числа также становятся заполненными.

Можно показать, что этот процесс всегда полностью заполняет все числа.

Так выглядит процесс при $$$k = 2$$$ и $$$n = 3$$$, где изначально $$$a_1 = \texttt{010}, a_5 = \texttt{110}$$$:

• Перед первым шагом заполнены числа с номерами $$$1, 5$$$. А значит, на этой операции будет выполнено $$$a_3 := a_1 \oplus a_5 = \texttt{010} \oplus \texttt{110} = \texttt{100}$$$.
• Перед вторым шагом заполнены числа с номерами $$$1, 3, 5$$$. А значит, на этой операции будет выполнено $$$a_2 := a_1 \oplus a_3 = \texttt{110}$$$ и $$$a_4 = a_{3} \oplus a_{5} = \texttt{010}$$$.

Вам необходимо посчитать следующее выражение: $$$x_1 \cdot y_1 + x_2 \cdot y_2 + \ldots + x_{2^k + 1} \cdot y_{2^k + 1}$$$, где $$$x_i$$$ — количество единичных битов в $$$i$$$-м числе, а $$$y_i$$$ — количество нулевых битов в $$$i$$$-м числе.