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.</p>

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₁⊕…⊕a_n=0, and
• a₁+a₂+…+a_n ≥ 1.

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

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.

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₁,…,m_n, separated by single spaces, 1 ≤ m_i < 2³² -1.

출력 형식

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⁶⁴.

예제 입력

3
2 1 3

예제 출력

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).