题目描述

吉吉国王去会见熊大和熊二，看到他们有许多袋饼干，第 $i$ 个袋子里有 $a_i$ 块饼干。狡猾的吉吉国王打算偷走其中一袋饼干，但是又不想让熊大和熊二在分饼干时出现不能均分的尴尬情况，于是他希望在拿走一饼干后，使得剩余所有袋子中饼干的总数是个大于 $0$ 的偶数。请问：吉吉国王有几种偷饼干的方案？

输入格式

第一行：一个整数 $n$，表示饼干的袋数

第二行：$n$ 个整数，分别表示每袋饼干的数量

输出格式

一个整数，表示方案总数

样例

6
10 11 12 14 20 25

4

样例 $1$ 解释

拿走第 $1,3,4,5$ 袋饼干中的任意一袋，都可以使剩下的饼干总数是一个偶数。

数据规模与约束

对于 $80\%$ 的数据，$1≤n,a_i≤100$；

对于 $100\%$ 的数据，$1≤n,a_i≤10^5$。