题目描述

给定一个长度为 $n$ 的序列 $\{a_i\}$，求有多少种方案可以将这 $n$ 个数划分成若干个区间，并使得每段区间所有数的和模 $10^9 + 7$ 的结果为偶数。

答案对 $10^9 + 7$ 取模。

输入格式
第一行一个正整数 $n$，表示序列长度。
第二行 $n$ 个整数 $a_i$，保证 $0 \leq a_i < 10^9+7$。

输出格式
一行一个整数，表示答案对 $10^9 + 7$ 取模的结果。

样例
输入

4
1000000006 1 5 1000000004

输出

3

三种划分方式如下
$[1000000006, 1, 5, 1000000004]$
$[1000000006, 1], [5, 1000000004]$
$[1000000006], [1, 5], [1000000004]$

数据范围与提示
$1 \leq n \leq 3 \times 10^5$
$0 \leq a_i \leq 10^9+7$