题目背景

有没有发现少了什么？

我们的 miku 决定出门逛街了。但是好巧不巧的就是她家里的装饰物少的可怜，并且只有一些数字可以作为装饰。

但是 miku 发现如果有若干个装饰物组成的数集 $A$，那么 $A$ 的子集 $f(A)$ 是最好看的（尽管不知道为什么）。所以就有了这道题。

但是因为看到了标题，所以聪明的你应该知道 miku 要去哪里了（误）。

题目描述

给定不重集合 $A$，定义其 装饰子集

这里的 $\texttt{“|”}$ 表示按位或；这里 $b\in A-\{a\}$ 表示 $b\in A$ 且 $b\not=a$。

miku 有一个长度为 $n$ 的正整数序列 $a_i$。你要给这个序列连续地划分为若干个（至少一个）连续子串。要求这些连续子串元素所组成的不重集合的 装饰子集 相同。

求方案数对 $10^9+7$ 取模。

输入格式

第一行一个正整数表示 $n$。

接下来长度为 $n$ 的正整数序列表示 $a_i$。

输出格式

一行一个正整数表示答案。

10
1 2 3 4 5 5 4 3 2 1

2

9
1 2 2 1 1 1 2 2 1

16

提示

【样例#1解释】 可以证明，两种方法分别是：

这里三个子集所组成的不重集合都是 $\{1,2,3,4,5\}$。它们的装饰子集都是 $\{3,5\}$。具体说明如下：

• $1:1|3=3$，故不属于。
• $2:2|3=3$，故不属于。
• $3:3|1=3,3|2=3,3|4=7,3|5=7$，故属于。
• $4:4|5=5$，故不属于。
• $5:5|1=5,5|2=7,5|3=7,5|4=5$，故属于。

本题采用捆绑测试

• $\text{subtask1(5pts)}:n\leq10$。
• $\text{subtask2(10pts)}:a_i\leq7$。
• $\text{subtask3(20pts)}:a_i=2^a+2^b$。其中 $a\not = b$。
• $\text{subtask4(20pts)}:a_i=2^a+2^b$。其中不保证 $a\not =b$。
• $\text{subtask5(10pts)}:$ 保证 $a_i$ 随机生成。
• $\text{subtask6(35pts)}:$ 无特殊限制。时限为 $3s$。

对于 $100\%$ 的数据，保证 $1\leq n\leq 3\times10^6,0\leq a_i\leq2\times 10^6$。