题目描述

题目译自 XIII OI Olimpiada Informatyczna – III etap Kryształy

Bajtocy 研究出一种制造晶体的方法，这种晶体由不同元素的特定数量原子组成。经过多年的实验，他成功找到了一个公式，该公式描述了对于各个元素原子的何种数量组合，可以制造出由这些原子构成的晶体。他很好奇自己能够获得多少种不同的晶体。

设 $x$ 和 $y$ 为非负整数。我们用 $x \oplus y$ 表示对 $x$ 和 $y$ 的对应二进制位执行异或（XOR）运算的结果。异或运算在二进制位上的结果如下：$1 \oplus 1 = 0 \oplus 0 = 0, 1 \oplus 0 = 0 \oplus 1 = 1$。

举个样例，$44 \oplus 6 = (101100)_2 \oplus (000110)_2 = (101010)_2 = 42$。

Bajtocy 知道 $n$ 种不同的元素，编号从 $1$ 到 $n$。对于每种元素 $i$，在制造晶体时，能够使用的该元素原子数量都有一个上限 $m_i$。要制造一个由第 $i$ 种元素的 $a_i$ 个原子（对于 $i=1, \ldots, n$）组成的晶体，当且仅当满足以下条件时才可能：

• $0 \le a_i \le m_i$，对于 $i=1, 2, \ldots, n$，
• $a_1 \oplus \ldots \oplus a_n = 0$，并且
• $a_1 + a_2 + \cdots + a_n \ge 1$。

上述最后一个条件意味着，一个晶体必须由至少一个原子构成。

请编写一个程序，实现以下功能：

• 从标准输入读取元素的数量以及在晶体中每种元素原子数量的限制。
• 计算出可以获得的不同晶体的数量。
• 将结果输出到标准输出。

输入格式

输入的第一行包含元素的数量 $n$ $(2 \le n \le 50)$。

输入的第二行也是最后一行，包含 $n$ 个由单个空格隔开的数字 $m_1, \ldots, m_n$ $(1 \le m_i < 2^{32}-1)$。

输出格式

你的程序应向标准输出输出一个数字，表示可以获得的晶体数量。你可以假设这个数字小于 $2^{64}-1$。

3
2 1 3

5

可能的各种元素原子数量组合为：$(0, 1, 1), (1, 0, 1), (1, 1, 0), (2, 0, 2), (2, 1, 3)$。