题目描述

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

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

输入一个长度为 $ n $ 的数列 $ a_1, a_2 , \dots, an $ 问有多少个长度大于等于 $ 2 $ 的不上升的子序列 $ a{b1}, a{b2}, \ldots, a{b_k} $ 满足

$$ \prod\limits{i = 2} ^ k \binom{a{b{i - 1}}}{a{bi}} \bmod 2 = \binom{a{b1}}{a{b2}} \times \binom{a{b2}}{a{b3}} \times \cdots \times \binom{a{b{k - 1}}}{a{b_k}}\bmod 2 > 0 $$

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

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

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

$$ 1 \leq b_1 < b2 < \cdots < b{k - 1} < b_k \leq n $$

我们称 $ a_{b1}, a{b2}, \ldots, a{b_k} $ 是 $ a $ 的一个子序列。

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

$$ a_{b1} \geq a{b2} \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_{bi}} $ 中一定有 $ 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 $。

输出格式

一行一个整数表示答案。

样例

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 $。