Để thay đổi không khí trong giờ số học, thầy giáo cho cả lớp bài kiểm tra ngắn như sau: Xác định số nghiệm nguyên của hệ ẩn ~x_1, x_2, \dots, x_N~: ~x_1 \oplus x_2 \oplus \dots \oplus x_N = 0~ ~0 \le x_i \le m_i~ (~\forall i = 1 \div N~) ~x_1 + x_2 + \dots + x_N \ge 1~ trong đó ~m_1, m_2, \dots, m_N~ là các tham số nguyên dương cho trước.

Không khí cả lớp sau khi đọc đề chẳng thay đổi chút nào, để cải thiện tình hình các bạn quyết định lén sang nhờ đội tuyển Tin lập trình xác định trước kết quả để sau đó … mò.

Yêu cầu: Xác định số nghiệm nguyên của hệ phương trình trên.

Input

• Dòng 1: số nguyên ~N~ (~2 \le N \le 50~)
• Dòng 2: ~N~ số nguyên ~m_1, m_2, \dots, m_N~ (~1 \le m_i < 2^{31}~)

Output

• Dòng 1: số nguyên kết quả (được đảm bảo trong phạm vi số nguyên 64 bit không dấu)

Sample Input 1

3
2 1 3

Sample Output 1

5