题目描述

题目译自 PA 2021 Runda 3 Mopadulo

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

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

输入格式

第一行一个正整数 $n$ ，表示序列长度 。

第二行 $n$ 个整数 $a_i$，保证 $0 \leq a_i \lt 10^9+7$ 。

输出格式

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

4
1000000006 1 5 1000000004

3

数据范围与提示

$1 \leq n \leq 3 \times 10 ^ 5$

$0 \leq a_i \lt 10 ^ 9 + 7$