Crystals

Byteman is a scientist who studies how crystals form from the atoms of different elements. He has designed a special process for growing crystals and derived a formula that describes which combinations of atoms make a valid crystal. He now wants to know how many different crystals his process can produce.

For non-negative integers $x$ and $y$, let $x \oplus y$ denote their bitwise exclusive or (XOR). On single bits it is defined by $1 \oplus 1 = 0 \oplus 0 = 0$ and $0 \oplus 1 = 1 \oplus 0 = 1$.

There are $n$ elements, numbered from $1$ to $n$. For each element $i$ there is an upper bound $m_i$ on the number of atoms of that element that a single crystal may contain. A crystal that uses $a_i$ atoms of element $i$ (for $i = 1, \dots, n$) can be formed if and only if:

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

The last condition simply states that every crystal must contain at least one atom. Two crystals are considered different if they differ in the number of atoms of at least one element.

Write a program that reads the number of elements and the per-element upper bounds, computes the number of different crystals that can be formed, and prints that number.

The first line contains the number of elements $n$ ($1 \le n \le 50$). The second line contains $n$ positive integers $m_1, \dots, m_n$ separated by single spaces, where $1 \le m_i < 2^{32} - 1$.

Print a single integer: the total number of different crystals that can be formed. This number is guaranteed to be smaller than $2^{64}$.

For the input with $n = 3$ and upper bounds $2\ 1\ 3$, the answer is $5$. Written as $(a_1, a_2, a_3)$, the five crystals are $(0, 1, 1)$, $(1, 0, 1)$, $(1, 1, 0)$, $(2, 0, 2)$, and $(2, 1, 3)$.