Calibration Module Signature Sum

EasyArrayMathBacktrackingBit manipulationCombinatoricsEnumeration2 sample tests6 hidden tests

A research submarine carries n calibration modules mounted in a rack; each module continuously broadcasts one integer signature value. For any chosen non-empty subset of modules, define that subset's "combined signature" as the bitwise XOR of the signature values of exactly the modules in the subset. Compute the sum, taken over every one of the 2^n - 1 non-empty subsets of modules, of that subset's combined signature.

Input format

Line 1: an integer n, the number of modules.
Line 2: n space-separated integers a_1 ... a_n, the signature broadcast by each module.

Output format

Print a single integer: the sum of the combined signatures of all non-empty subsets of modules.

Constraints

1 <= n <= 12
1 <= a_i <= 20

Examples

Example 1

Input

2
1 3

Expected

Explanation

The non-empty subsets of modules {1,3} are {1} (signature 1), {3} (signature 3), and {1,3} (signature 1 XOR 3 = 2). Summing 1 + 3 + 2 gives 6.

Example 2

Input

3
5 1 6

Expected

Explanation

The non-empty subsets of {5,1,6} give combined signatures 5, 1, 6, 5^1=4, 5^6=3, 1^6=7, and 5^1^6=2. Summing 5+1+6+4+3+7+2 gives 28.

Ready to solve this?