問題文

$2$ つの長さ $N$ の整数列 $x_1, x_2, ..., x_N$ と $y_1, y_2, ..., y_N$ が「似ている」とは、 任意の $i$ ($1 \\leq i \\leq N$) に対して $|x_i - y_i| \\leq 1$ が成り立つことをいうものとします。

とくに、どの整数列もその数列自身と似ていると考えます。

整数 $N$ および長さ $N$ の整数列 $A_1, A_2, ..., A_N$ が与えられます。

$A$ と似ている整数列 $b_1, b_2, ..., b_N$ であって、すべての項の積 $b_1 b_2 ... b_N$ が偶数となるものはいくつあるか求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

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

出力

条件を満たす整数列の個数を出力せよ。

入力例 1

2
2 3

出力例 1

7

条件を満たす整数列は以下の $7$ 個あります。

• $1, 2$
• $1, 4$
• $2, 2$
• $2, 3$
• $2, 4$
• $3, 2$
• $3, 4$

入力例 2

3
3 3 3

出力例 2

26

入力例 3

1
100

出力例 3

1

入力例 4

10
90 52 56 71 44 8 13 30 57 84

出力例 4

58921