题目描述

我们称两个长度为 $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$。

有多少个整数序列 $b_1, b_2, ..., b_N$ 满足 $b_1, b_2, ..., b_N$ 与 $A$ 相似，并且所有元素的乘积 $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

满足条件的整数序列有七个：

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