Similar Arrays

给定一个数组 $a$，求有多少个数组 $b$，使得数组 $b$ 的每一个值都与数组 $a$ 相似，且数组 $b$ 的所有值之积为偶数。

[problemUrl]: https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_b $ 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 $ が偶数となるものはいくつあるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

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

2
2 3

7

3
3 3 3

26

1
100

1

10
90 52 56 71 44 8 13 30 57 84

58921

### 制約 - $ 1\ \leq\ N\ \leq\ 10 $ - $ 1\ \leq\ A_i\ \leq\ 100 $ ### Sample Explanation 1 条件を満たす整数列は以下の $ 7 $ 個あります。 - $ 1,\ 2 $ - $ 1,\ 4 $ - $ 2,\ 2 $ - $ 2,\ 3 $ - $ 2,\ 4 $ - $ 3,\ 2 $ - $ 3,\ 4 $