简单的题目，既是礼物，也是毒药。
B 君设计了一道简单的题目，准备作为 gift 送给大家。
输入一个长度为 $n$ 的数列 $a_1,a_2,⋯,a_n$ 问有多少个长度大于等于 2 的不上升的子序列满足：
$\prod_{i=2}^k \begin{pmatrix} a_{b_{i-1}} \\ a_{b_i} \end{pmatrix} \mod 2= \begin{pmatrix} a_{b_1} \\ a_{b_2} \end{pmatrix} \times \begin{pmatrix} a_{b_2} \\ a_{b_3} \end{pmatrix} \times \cdots \times \begin{pmatrix} a_{b_{k-1}} \\ a_{b_k} \end{pmatrix} \mod 2 > 0$
输出这个数对 $1000000007$ 取模的结果。
G 君看到题目后，为大家解释了一些基本概念。
我们选择任意多个整数 $b_i$ 满足
$1≤b_1<b_2<⋯<b_{k−1}<b_k≤n$
我们称 $a_{b_1},a_{b_2},⋯,a_{b_k}$ 是 $a$ 的一个子序列。
如果这个子序列同时还满足
$a_{b_1}≥a_{b_2}≥⋯≥a_{b_{k−1}}≥a_{b_k}$
我们称这个子序列是不上升的。
组合数 $\begin{pmatrix} n \\ m \end{pmatrix}$ 是从 $n$ 个互不相同的元素中取 $m$ 个元素的方案数，具体计算方案如下：
$\begin{pmatrix} n \\ m \end{pmatrix}=\frac{n!}{m!(n-m)!}=\frac{n \times (n-1) \times \cdots \times 2 \times 1}{(m \times(m-1)\times \cdots \times 2 \times 1)((n-m) \times (n-m-1) \times \cdots \times 2 \times 1)}$
这里要特别注意，因为我们只考虑不上升子序列，所以在求组合数的过程中，一定满足 $n≥m$，也就是 $\begin{pmatrix} a_{b_{i-1}} \\ a_{b_i} \end{pmatrix}$ 中一定有 $a_{b_{i-1}}≥a_{b_i}$。
我们在这里强调取模 $x \mod y $ 的定义：
$x \mod y=x- \lfloor \frac{x}{y} \rfloor \times y$
其中 $⌊n⌋$ 表示小于等于 $n$ 的最大整数。
$x \mod2>0$，就是在说 $x$ 是奇数。
与此同时，经验告诉我们一个长度为 $n$ 的序列，子序列个数有 $O(2^n)$ 个，所以我们通过对答案取模来避免输出过大。
B 君觉得 G 君说的十分有道理，于是再次强调了这些基本概念。
最后，G 君听说这个题是作为 gift 送给大家，她有一句忠告。
“Vorsicht, Gift!”
“小心……剧毒！ ”
Comet OJ