Crystals

Memory limit: 32 MB

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 and , by we shall denote their bit-wise xor. The basic xor for single bits is defined by: , .

Byteman knows different elements that can be used to create crystals - these are numbered from to . For each element there is an upper bound on number of atoms of this element that can be used to create a crystal. Byteman can create one unique crystal composed of atoms of the element (for ), if and only if:

• for ,
• , and
• .

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 , . The second, last line of the standard input contains positive integers , separated by single spaces, .

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 .

Example

For the input data:

3
2 1 3

the correct result is:

5

And the following are every possible numbers of atoms of each particular element: , , , , .

Task author: Jakub Pawlewicz.