#2264. 「CTSC2017」吉夫特

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

题目描述

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

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

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

i=2k(abi1abi)mod2=(ab1ab2)×(ab2ab3)××(abk1abk)mod2>0 \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 1000000007 取模的结果。

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

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

1b1<b2<<bk1<bkn 1 \leq b_1 < b_2 < \cdots < b_{k - 1} < b_k \leq n

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

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

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

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

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

(nm)=n!m!(nm)!=n×(n1)××2×1(m×(m1)××2×1)((nm)×(nm1)××2×1) \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)}

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

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

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

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

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

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

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

输入格式

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

输出格式

一行一个整数表示答案。

样例

样例输入

4
15
7
3
1

样例输出

11

数据范围与提示

对于前 10% 10\% 的测试点,n9,1ai13 n \leq 9, 1 \leq a_i \leq 13
对于前 20% 20\% 的测试点,n17,1ai20 n \leq 17, 1 \leq a_i \leq 20
对于前 40% 40\% 的测试点,n1911,1ai4000 n \leq 1911, 1 \leq a_i \leq 4000
对于前 70% 70\% 的测试点,n2017 n \leq 2017
对于前 85% 85\% 的测试点,n100084 n \leq 100084
对于 100% 100\% 的测试点,1n211985,1ai233333 1 \leq n \leq 211985, 1 \leq a_i \leq 233333

所有的 ai a_i 互不相同,也就是说不存在 i,j i, j 同时满足 1i<jn 1 \leq i < j \leq n ai=aj a_i = a_j