Problem Description

Two integer sequences of length $ N $, $ x_1, x_2, ..., x_N $ and $ y_1, y_2, ..., y_N $, are considered "similar" if for any $ i $ ($1 \leq i \leq N$), $|x_i - y_i| \leq 1$ holds.

In particular, any integer sequence is considered similar to itself.

You are given an integer $ N $ and an integer sequence of length $ N $, $ A_1, A_2, ..., A_N $.

Find the number of integer sequences $ b_1, b_2, ..., b_N $ that are similar to $ A $ and where the product of all terms $ b_1 b_2 ... b_N $ is even.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the number of integer sequences that satisfy the conditions.

Sample Input and Output

Sample Input #1

2
2 3

Sample Output #1

7

Sample Input #2

3
3 3 3

Sample Output #2

26

Sample Input #3

1
100

Sample Output #3

1

Sample Input #4

10
90 52 56 71 44 8 13 30 57 84

Sample Output #4

58921

Notes/Hints

Constraints

• $1 \leq N \leq 10$
• $1 \leq A_i \leq 100$

Sample Explanation 1

The following 7 sequences satisfy the conditions:
- $ 1, 2 $
- $ 1, 4 $
- $ 2, 2 $
- $ 2, 3 $
- $ 2, 4 $
- $ 3, 2 $
- $ 3, 4 $

见题面 Input 部分

见题面 Output 部分