#2264. 「CTSC2017」吉夫特

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

输入一个长度为 n 的数列 a_1, a_2 , \dots, a_n 问有多少个长度大于等于 2 的不上升的子序列 a_{b_1}, a_{b_2}, \ldots, a_{b_k} 满足

\prod\limits_{i = 2} ^ k \binom{a_{b_{i - 1}}}{a_{b_i}} \bmod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \times \binom{a_{b_{k - 1}}}{a_{b_k}}\bmod 2 > 0

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

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

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

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

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

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

a_{b_1} \geq a_{b_2} \geq \ldots \geq a_{b_k}

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

组合数 \binom{n}{m} 是从 n 个互不相同的元素中取 m 个元素的方案数,具体计算方法如下:

\binom{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 \geq m ,也就是 \binom{a_{b_{i - 1}}}{a_{b_i}} 中一定有 a_{b_{i - 1}} \geq a_{b_i}

我们在这里强调取模 x \bmod y 的定义:

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

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

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

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

B 君觉得 G 君说的十分有道理,于是再次强调了这些基本概念。
最后,G 君听说这个题是作为 gift 送给大家,她有一句忠告。
“Vorsicht, Gift!”
‘‘小心. . . . . . 剧毒!”

输入格式

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

输出格式

一行一个整数表示答案。

样例

样例输入

4
15
7
3
1

样例输出

11

数据范围与提示

对于前 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