3840. [CTSC 2017] 吉夫特

【题目描述】

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

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

输入一个长度为  $n$  的数列  $a_1, a_2, \cdots , a_n$  问有多少个长度大于等于  $2$  的不上升的子序列满足：

$\prod _{i=2}^{k} \left( \begin{array}{c} a_{b_{i-1}} \\ a_{b_i} \end{array} \right) \bmod 2 = \left( \begin{array}{c} a_{b_1} \\ a_{b_2} \end{array} \right) \times \left( \begin{array}{c} a_{b_2} \\ a_{b_3} \end{array} \right) \times \cdots \left( \begin{array}{c} a_{b_{k-1}} \\ a_{b_k} \end{array} \right) \bmod 2 > 0$

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

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

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

$1 \leq b_1 < b_2 < \dots < b_{k-1} < b_k \leq n$

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

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

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

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

组合数  $\left( \begin{array}{c} n \\ m \end{array} \right)$  是从  $n$  个互不相同的元素中取  $m$  个元素的方案数，具体计算方案如下：

$\left( \begin{array}{c} n \\ m \end{array} \right)=\frac{n!}{m!(n-m)!}=\frac{n \times (n-1) \times \cdots \times 2 \times 1}{(m \times (m-1) \cdots \times 2 \times 1)((n-m)\times(n-m-1)\times \cdots \times 2 \times 1)}$

这里要特别注意，因为我们只考虑不上升子序列，所以在求组合数的过程中，一定满足  $n \geq m$ ，也就是 $\left( \begin{array}{c} a_{b_{i-1}} \\ a_{b_i} \end{array} \right)$ 中一定有 $a_{b_{i-1}} \geq a_{b_i}$ 。

我们在这里强调取模  $x \mod y$  的定义：

$x \bmod y = x -\left \lfloor \frac{x}{y} \right \rfloor \times y$

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

$x \bmod 2 > 0$  ，就是在说  $x$  是奇数。

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

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

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

“Vorsicht, Gift!”

“小心. . . . . .剧毒！ ”

【输入格式】

第一行一个整数 $n$。

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

【输出格式】

一行一个整数表示答案。

【样例1输入】

4
15
7
3
1

【样例1输出】

11

【样例2/3】

点击下载样例2/3 

【数据规模与约定】

对于前 $10\%$ 的测试点，$n \leq 9$，$1\leq a_i\leq 13$。

对于前 $20\%$ 的测试点，$n\leq 17$，$1\leq a_i\leq 20$。

对于前 $40\%$ 的测试点，$n\leq 1911$，$1\leq a_i\leq 4000$。

对于前 $70\%$ 的测试点，$n\leq 2017$。

对于前 $85\%$ 的测试点，$n\leq 100084$。

对于 $100\%$ 的测试点，$1\leq n\leq 211985$，$1\leq a_i\leq 233333$。所有的 $a_i$ 互不相同，也就是说不存在 $i, j$ 同时满足 $1\leq i < j\leq n$ 和 $a_i = a_j$。