In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

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.

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

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 .

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