Statement

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 theamount of elements that can be used to create a crystal. Now, he wonders how many differentcrystals can be created in such process.

For non-negative integers $x$ and $y$, by $x\bigoplus y$ we shall denote their bit-wise xor. The basic xor forsingle bits is defined by:

$1\bigoplus 1=0\bigoplus 0=0$,$0\bigoplus 1=1\bigoplus 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 $m_i$ on number of atoms of this elementthat can be used to create a crystal. Byteman can create one unique crystal composed of $a_i$ atomsof the element $i$ (for $i=1,\cdots,n$), if and only if:

• $0\le a_i\le m_i$ for $i=1,\cdots,n$
• $a_1\bigoplus\cdots\bigoplus a_n=0$, and
• $a_1+a_2+\cdots+a_n\ge 1$.

Note that the last condition is quite obvious and essentially states that every crystal is composed ofat least one atom.

TaskWrite 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 Format

The first line of the standard input contains the number of elements $n$, $1\le n\le 50$.

The second, last line of the standard input contains $n$ positive integers $m_1,\cdots,m_n$, separated by single spaces,$1\le m_i < 2^{32}-1$.

Output Format

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}$.

3
2 1 3

5