XOR-Weighted Subset Product

God is tutoring His child in math. When God criticized the child for his miscalculation in mental arithmetic – a result that was off by several digits and took an absurdly small 0.000...00215055865 seconds – the child spotted you and demanded that you verify the result.

You couldn’t possibly recompute it exactly as God did, so you pleaded for a reduction in data size. God agreed and said: "You are a brave explorer, and once you finish this problem, we shall be friends."

The problem is as follows:

Given a positive integer n and a sequence of natural numbers \(a_1,a_2,\cdots,a_n\), for each integer \(S\) with \(0\le S\le2^n-1\) you need to compute its "weight" \(v(S)\). The weight is defined by writing \(S\) in binary and, for each bit, if the \(x\)-th bit (counting from the least significant bit, starting with \(x=1\)) is \(1\) then you XOR (\(\oplus\)) the current answer with \(a_x\). In other words, \[ v(S)=\bigoplus_{x:\,S_x=1} a_x. \]

After computing \(v(S)\) for each \(S\), multiply each \(v(S)\) with its corresponding \(S\) and then take the cumulative bitwise XOR of all these products. Formally, you need to compute:

\[ \text{answer} = \left( \bigoplus_{S=0}^{2^n-1} \Big(S \times v(S)\Big) \right) \bmod 2^{64}. \]

Your task is to compute and output this final answer.

inputFormat

The first line contains a positive integer n (the number of elements in the sequence). The second line contains n space-separated natural numbers \(a_1,a_2,\cdots,a_n\).

It is guaranteed that \(0\le S\le2^n-1\) makes it feasible to iterate over all subsets.

outputFormat

Output a single unsigned 64-bit integer representing the final answer:

\[ \left(\bigoplus_{S=0}^{2^n-1} (S \times v(S))\right) \bmod 2^{64}. \]</p>

sample

1
5

5