Crystal Composition Problem

Byteman is a scientist who investigates the creation of crystals consisting of atoms of different elements.

He has designed a special process for creating crystals and 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 using this process.

For non‐negative integers \(x\) and \(y\), we denote their bit‐wise xor by \(x \bigoplus y\). The xor for single bits is defined as follows:

\[ 1 \bigoplus 1 = 0, \quad 0 \bigoplus 0 = 0, \quad 0 \bigoplus 1 = 1, \quad 1 \bigoplus 0 = 1. \]

Byteman knows \(n\) different elements numbered from \(1\) to \(n\) that can be used for creating crystals. For each element \(i\), there is an upper bound \(m_i\) on the number of atoms of that element that can be used. A unique crystal composed of \(a_i\) atoms of element \(i\) (for \(i=1,\dots,n\)) can be created if and only if:

• \(0 \le a_i \le m_i\) for \(i=1,\dots,n\),
• \(a_1 \bigoplus a_2 \bigoplus \cdots \bigoplus a_n = 0\), and
• \(a_1+a_2+\cdots+a_n \ge 1\) (i.e. the crystal is non-empty).

Your task is to compute the number of different crystals that can be created.

inputFormat

The input is read from the standard input and has the following format:

The first line contains a single integer \(n\) representing the number of elements.
The second line contains \(n\) space-separated integers \(m_1, m_2, \dots, m_n\) where \(m_i\) is the upper bound on the number of atoms of element \(i\).

outputFormat

Output a single integer: the number of different crystals that can be created following the above rules.

sample

2
1 1

1