Byteman 是一位研究不同元素原子构成晶体的科学家。他设计了一种特殊的晶体制造工艺，并发现了一个公式，可以确定制造晶体时所能使用的元素数量。现在，他想知道在这种工艺下可以制造出多少种不同的晶体。

对于非负整数 $x$ 和 $y$，我们用 $x \oplus y$ 表示它们的按位异或运算。单个比特的基本异或运算定义为：$1 \oplus 1 = 0 \oplus 0 = 0$，$0 \oplus 1 = 1 \oplus 0 = 1$。

Byteman 知道 $n$ 种可用于制造晶体的不同元素，编号从 $1$ 到 $n$。对于每种元素 $i$，都有一个可用于制造晶体的原子数量上限 $m_i$。Byteman 可以制造出一种由 $a_i$ 个元素 $i$ 的原子组成的独特晶体（对于 $i=1, \dots, n$），当且仅当满足以下条件：

• $0 \le a_i \le m_i$，对于 $i=1, \dots, n$，
• $a_1 \oplus \dots \oplus a_n = 0$，以及
• $a_1 + a_2 + \dots + a_n \ge 1$。

注意，最后一个条件非常直观，本质上说明每个晶体至少由一个原子组成。

任务

编写一个程序，完成以下工作：

• 从标准输入读取：元素的数量以及每种元素原子数量的上限，
• 计算可以制造出的不同晶体的数量，
• 将结果写入标准输出。

输入格式

标准输入的第一行包含元素的数量 $n$，$1 \le n \le 50$。第二行（最后一行）包含 $n$ 个正整数 $m_1, \dots, m_n$，以空格分隔，$1 \le m_i < 2^{32} - 1$。

输出格式

你的程序应向标准输出写入一个整数，即可以制造出的不同晶体的总数。你可以假设该数字小于 $2^{64}$。

样例

输入 1

3
2 1 3

输出 1

5

说明 1

以下是每种元素原子数量的所有可能组合：(0,1,1), (1,0,1), (1,1,0), (2,0,2), (2,1,3)。