결정

바이트맨(Byteman)은 서로 다른 원소의 원자로 결정(crystal)이 어떻게 만들어지는지를 연구하는 과학자입니다. 그는 결정을 성장시키는 특별한 공정을 설계했고, 어떤 원자 조합이 유효한 결정을 이루는지 알려 주는 공식을 찾아냈습니다. 이제 그는 이 공정으로 서로 다른 결정을 몇 개나 만들 수 있는지 알고 싶어 합니다.

음이 아닌 두 정수 $x$, $y$에 대해 $x \oplus y$는 두 수의 비트 단위 배타적 논리합(XOR)을 나타냅니다. 한 비트에 대한 정의는 $1 \oplus 1 = 0 \oplus 0 = 0$, $0 \oplus 1 = 1 \oplus 0 = 1$입니다.

원소는 $1$번부터 $n$번까지 모두 $n$개가 있습니다. 각 원소 $i$에는 하나의 결정에 쓸 수 있는 원자 수의 상한 $m_i$가 정해져 있습니다. 각 원소 $i$의 원자를 $a_i$개씩 사용한 결정은 다음 조건을 모두 만족할 때에만 만들 수 있습니다.

• 모든 $i = 1, \dots, n$에 대해 $0 \le a_i \le m_i$,
• $a_1 \oplus a_2 \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}$보다 작음이 보장됩니다.

$n = 3$이고 상한이 $2\ 1\ 3$인 입력에서 답은 $5$입니다. 다섯 개의 결정을 $(a_1, a_2, a_3)$ 형태로 쓰면 $(0, 1, 1)$, $(1, 0, 1)$, $(1, 1, 0)$, $(2, 0, 2)$, $(2, 1, 3)$입니다.