题目描述

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

由于结果可能很大，你只需要求出结果对 $10^9 + 7$ 取模的值。

输入格式

第一行，一个整数 $n$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$。

输出格式

一行，一个整数，表示所求的值。

4
1000000006 1 5 1000000004

3

提示

样例 #1 解释

三种划分方式如下：

• $[1, 4]$
• $[1, 2], [3, 4]$
• $[1], [2, 3], [4]$

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 3 \times 10^5$，$0 \leq a_i < 10^9 + 7$。