和为偶数的非空子集

题目描述

给定 n 个非负整数。一个子集通过选择若干个不同下标得到，选择顺序不影响子集；即使两个位置的数值相同，也视为不同的可选元素。求元素和为偶数的非空子集数量。

输入格式

第一行输入整数 n，满足 1≤n≤30。第二行输入 n 个整数 a1,a2,…,an，满足 0≤ai≤10^18。

输出格式

输出元素和为偶数的非空子集数量。答案在 64 位有符号整数范围内。

样例

输入

3
1 2 3

输出

3