Dãy tương tự 2

Hai dãy số nguyên \(x_1, x_2, ... , x_n\) và \(y_1, y_2, ... , y_n\) được gọi là tương tự nhau nếu \(|x_i −y_i| \le 1\)với mọi \(i\) \((1 \le i \le n).\)

Cho dãy số nguyên độ dài \(n\) gồm \(a_1, a_2, ... , a_n\).

Yêu cầu

Hãy đếm xem có bao nhiêu dãy số nguyên \(b_1, b_2, ... , b_n\) tương tự với dãy \((a)\) và tích các phần tử của dãy \((b)\) là số chẵn.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 25)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ... , a_n\) \((1 \le a_i \le 10^4)\).

Output

• In ra số lượng dãy số nguyên \(b\) thỏa mãn yêu cầu.

Example

2 
 2 3

7

3 
 3 3 3

26

Ràng buộc

• Có \(50\%\) tests có \(1 \leq n \leq 10\).