题目描述

给你一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，请求出有多少个长度不小于 $1$ 的子序列，满足该子序列数字之和为偶数。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数，表示 $a_1,a_2,...,a_n$。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

4
3 2 1 4

输出 #1

7

说明/提示

$1\le n\le 40,1\le a_i\le 10^9$