← 返回题目列表

AtCoder · code_festival_2017_qualc_b

B. 类似数组

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

我们会说两个长度的整数序列 N, x_1, x_2, ..., x_N 和 y_1, y_2, ..., y_N,是 类似 当 |x_i - y_i| \leq 1 适用于所有人 i (1 \leq i \leq N).

特别是,任何整数序列都与其自身相似。

给你一个整数 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