Byteman is a scientist who investigates creation of crystals consisting of atoms of different elements. He has designed a special process for creating crystals and has discovered a formula specifying the amount of elements that can be used to create a crystal. Now, he wonders how many different crystals can be created in such process.
For non-negative integers x and y, by x⊕y we shall denote their bit-wise xor. The basic xor for single bits is defined by: $1⊕1=0⊕0=0$, $0⊕1=1⊕0=1$.
Byteman knows n different elements that can be used to create crystals - these are numbered from $1$ to $n$. For each element i there is an upper bound mi on number of atoms of this element that can be used to create a crystal. Byteman can create one unique crystal composed of ai atoms of the element $i$ (for $i=1,…,n$), if and only if:
- $0 ≤ a_i ≤ m_i$ for $i=1,…,n$,
- $a_1⊕…⊕a_n=0$, and
- $a_1+a_2+…+a_n ≥ 1$.
Note that the last condition is quite obvious and essentially states that every crystal is composed of at least one atom.
Task
Write a programme which:
- reads form the standard input: the number of elements and the bounds on numbers of atoms of particular elements,
- computes the number of different crystals that can be created,
- writes the result to the standard output.
Input
The first line of the standard input contains the number of elements $n$, $1 ≤ n ≤ 50$. The second, last line of the standard input contains $n$ positive integers $m_1,…,m_n$, separated by single spaces, $1 ≤ m_i < 2^{32} -1$.
Output
Your programme should write one integer to the standard output - total number of different crystals that can be created. You can assume that this number is less than $2^{64}$.
Example
Input
3 2 1 3
Output
5
And the following are every possible numbers of atoms of each particular element: (0,1,1), (1,0,1), (1,1,0), (2,0,2), (2,1,3).