简单的题目，既是礼物，也是毒药。

B 君设计了一道简单的题目，准备作为 gift 送给大家。

输入一个长度为 $n$ 的数列 $a_1,a_2,\dots ,a_n$

问有多少个长度大于等于 $2$ 的不上升的子序列 $a_{b_1},a_{b_2},\dots ,a_{b_k}$ 满足

$$\prod _{i=2}^k(\genfrac{}{}{0ex}{}{a_{b_{i-1}}}{a_{b_i}})mod2=(\genfrac{}{}{0ex}{}{a_{b_1}}{a_{b_2}})\times (\genfrac{}{}{0ex}{}{a_{b_2}}{a_{b_3}})\times \cdots \times (\genfrac{}{}{0ex}{}{a_{b_{k-1}}}{a_{b_k}})mod2>0$$

输出这个个数对 $1000000007$ 取模的结果。

G 君看到题目后，为大家解释了一些基本概念。

我们选择任意多个整数 $b_i$ 满足

$$1\le b_1<b_2<\cdots <b_{k-1}<b_k\le n$$

我们称 $a_{b_1},a_{b_2},\dots ,a_{b_k}$ 是 $a$ 的一个子序列。

如果这个子序列同时还满足

$$a_{b_1}\ge a_{b_2}\ge \cdots \ge a_{b_{k-1}}\ge a_{b_k}$$

我们称这个子序列是不上升的。

组合数 $(\genfrac{}{}{0ex}{}{n}{m})$ 是从 $n$ 个互不相同的元素中取 $m$ 个元素的方案数，具体计算方法如下：

$$(\genfrac{}{}{0ex}{}{n}{m})=\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\ge m$，也就是 $(\genfrac{}{}{0ex}{}{a_{b_{i-1}}}{a_{b_i}})$ 中一定有 $a_{b_{i-1}}\ge a_{b_i}$。

我们在这里强调取模 $xmody$ 的定义：

$$xmody=x-\lfloor \frac{x}{y}\rfloor \times y$$

其中 $\lfloor n\rfloor$ 表示小于等于 $n$ 的最大整数。

$xmod2>0$，就是在说$x$是奇数。

与此同时，经验告诉我们一个长度为 $n$ 的序列，子序列个数有 $O(2^n)$ 个，所以我们通过对答案取模来避免输出过大。

B 君觉得 G 君说的十分有道理，于是再次强调了这些基本概念。

最后，G 君听说这个题是作为 gift 送给大家，她有一句忠告。

"Vorsicht, Gift!"

“小心……剧毒！”

输入格式

第一行一个整数$n$。

接下来$n$行，每行一个整数，这$n$行中的第$i$行，表示$a_i$。

输出格式

一行一个整数表示答案。

样例一

input

4
15
7
3
1

output

11

样例二至样例九

见样例数据下载。

限制与约定

• 对于前 $10\mathrm{\%}$ 的测试点，$n\le 9,1\le a_i\le 13$；
• 对于前 $20\mathrm{\%}$ 的测试点，$n\le 17,1\le a_i\le 20$；
• 对于前 $40\mathrm{\%}$ 的测试点，$n\le 1911,1\le a_i\le 4000$；
• 对于前 $70\mathrm{\%}$ 的测试点，$n\le 2017$；
• 对于前 $85\mathrm{\%}$ 的测试点，$n\le 100084$；
• 对于 $100\mathrm{\%}$ 的测试点， $1\le n\le 211985,1\le a_i\le 233333$。所有的$a_i$互不相同，也就是说不存在$i,j$同时满足$1\le i<j\le n$和$a_i=a_j$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载