累乘积

题目背景

空集是 \varnothing（$\varnothing$）。
—— by Somebody

数学课上，徐老师给 Alice 出了一道题：已知集合 $M=\left\{1,2,3,4\right\}$，设一个集合的累乘积为集合中所有元素的乘积。

特别地，$\varnothing$（空集）的累乘积为 $0$，问集合 $M$ 有多少个子集的累乘积为偶数。

题目描述

现在 Alice 又给你出了一道题，已知集合 $M$ 共有 $n$ 个元素，分别为 $m_1,m_2,...,m_n$，这些元素互不相同，请你求出 $M$ 有多少个子集的累乘积为偶数。

形式化地，已知集合 $M_n=\left\{m_1,m_2,...m_n\right\},M_0=\varnothing$，设 $f(\varnothing)=0,f(M_n)=\prod_{i=1}^nm_i$，求有多少个 $M_k\subseteq M_n$ 且 $f(M_k)\bmod2=0$

由于答案很大，请把答案对 $\bm{10^7+7}$ 取模。

输入格式

• 第一行一个正整数 $n$，表示集合 $M$ 元素个数。
• 第二行 $n$ 个互异的正整数，表示集合 $M$ 中的每个元素。（不保证有序）

输出格式

输出一行整数，表示满足条件的子集数。

样例 #1

样例输入 #1

4
1 2 4 3

样例输出 #1

13

样例 #2

样例输入 #2

3
2 4 6

样例输出 #2

8

提示

【数据范围】

• 对于 $10\%$ 的数据，保证 $M$ 中所有的元素是偶数；
• 对于另外 $20\%$ 的数据，保证 $4\le n\le 20$；
• 对于 $100\%$ 的数据，保证 $4\le n\le 10^6$，$0\le m_i\le10^7$。

【样例 1 说明】

满足条件的集合：$\varnothing,\left\{2\right\},\left\{4\right\},\left\{1,2\right\},\left\{1,4\right\},\left\{2,3\right\},\left\{2,4\right\},\left\{3,4\right\},\left\{1,2,3\right\},\left\{1,2,4\right\},\left\{1,3,4\right\},\left\{2,3,4\right\},\left\{1,2,3,4\right\}$。