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| ≤ 1\)với mọi \(i\) \((1 ≤ i ≤ 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 ≤ n ≤ 25)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ... , a_n\) \((1 ≤ a_i ≤ 10^4)\).

Output

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

Example

Ràng buộc

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