U478105 累乘积

数学课上，徐老师给Alice出了一道题：已知集合 $ M=\left\{1,2,3,4\right\}$ ，设一个集合的**累乘积**为**集合中所有元素的乘积**，**特别地**， $\phi$ （空集）的累乘积为 $0$ ,问集合$M$有多少个子集的累乘积为偶数

现在Alice又给你出了一道题，已知集合 $M$ 共有 $n$ 个元素，分别为 $m_1,m_2,...m_n$ ，这些元素互不相同，请你求出$M$有多少个子集的累乘积为偶数。由于答案很大，请输出答案**模** $10000007$ **的结果** 形式化地，已知集合 $M_n=\left\{m_1,m_2,...m_n\right\}，M_0=\phi，设n(\phi)=0,n(M_n)=\prod_{i=1}^nm_i$ ,求有多少个 $M_k\subseteq M_n $ 且 $ n(M_k)\mod2=0$ 的答案 $\mod10000007$

第一行一个正整数 $n$ ，表示集合 $M$ 元素个数 第二行 $n$ 个互异的正整数，表示集合 $M$ 中的每个元素

输出一行整数，表示满足条件的子集数目 $\mod10000007$ 的结果

对于 $10\%$ 的数据， $M$ 中所有的元素是偶数 对于另外 $20\%$ 的数据，保证 $4\le n\le 20$ 对于 $100\%$ 的数据，保证 $4\le n\le 10^6,0\le m_i\le10^7$ **本题需要较快的读入方式** **样例1说明** 满足条件的集合：$\phi,\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\}$