Background

Have you noticed that something is missing?

Our miku decided to go shopping. But by an unfortunate coincidence, there are very few decorations in her home, and she only has some numbers that can be used as decorations.

However, miku found that if there is a set of numbers $A$ formed by several decorations, then the subset $f(A)$ of $A$ is the best-looking one (although we do not know why). So this problem was created.

But since you have seen the title, you should know where miku is going (just kidding).

Problem Description

Given a set without duplicates $A$, define its decorative subset as

Here, $\texttt{"|"}$ denotes bitwise OR. Also, $b\in A-\{a\}$ means $b\in A$ and $b\not=a$.

miku has a positive integer sequence $a_i$ of length $n$. You need to partition this sequence into several (at least one) contiguous substrings. It is required that the decorative subsets of the sets without duplicates formed by the elements of these substrings are the same.

Compute the number of valid partitioning schemes modulo $10^9+7$.

Input Format

The first line contains one positive integer $n$.

The next line contains a positive integer sequence of length $n$, representing $a_i$.

Output Format

Output one positive integer, the answer.

10
1 2 3 4 5 5 4 3 2 1

2

9
1 2 2 1 1 1 2 2 1

16

Hint

[Explanation for Sample #1] It can be proven that the two ways are:

The sets without duplicates formed by these three subsets are all $\{1,2,3,4,5\}$. Their decorative subsets are all $\{3,5\}$. The details are as follows:

• $1:1|3=3$, so it does not belong.
• $2:2|3=3$, so it does not belong.
• $3:3|1=3,3|2=3,3|4=7,3|5=7$, so it belongs.
• $4:4|5=5$, so it does not belong.
• $5:5|1=5,5|2=7,5|3=7,5|4=5$, so it belongs.

This problem uses bundled testdata.

• $\text{subtask1(5pts)}:n\leq10$.
• $\text{subtask2(10pts)}:a_i\leq7$.
• $\text{subtask3(20pts)}:a_i=2^a+2^b$. Where $a\not = b$.
• $\text{subtask4(20pts)}:a_i=2^a+2^b$. Where it is not guaranteed that $a\not =b$.
• $\text{subtask5(10pts)}:$ It is guaranteed that $a_i$ is generated randomly.
• $\text{subtask6(35pts)}:$ No special restrictions. The time limit is $3s$.

For $100\%$ of the data, it is guaranteed that $1\leq n\leq 3\times10^6,0\leq a_i\leq2\times 10^6$.

Input Format

The first line contains one positive integer $n$.

The next line contains a positive integer sequence of length $n$, representing $a_i$.

Output Format

Output one positive integer, the answer.

Hint

Constraints: For $100\%$ of the data, it is guaranteed that $1\leq n\leq 3\times10^6,0\leq a_i\leq2\times 10^6$.

Translated by ChatGPT 5