配点: $200$ 点

問題文

$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$

出力

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

2
2 3

7

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

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

3
3 3 3

26

1
100

1

10
90 52 56 71 44 8 13 30 57 84

58921