简单的题目,既是礼物,也是毒药。
B 君设计了一道简单的题目,准备作为 gift 送给大家。
输入一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$
问有多少个长度大于等于 $2$ 的不上升的子序列 $a_{b_1}, a_{b_2}, \ldots ,a_{b_k}$ 满足
$$\prod_{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 \cdots \geq a_{b_{k-1}} \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 - \left \lfloor \frac{x}{y} \right \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$。
输出格式
一行一个整数表示答案。
样例一
input
4 15 7 3 1
output
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$。
时间限制:$2\texttt{s}$
空间限制:$512\texttt{MB}$