Problem Description

Given a non-negative integer sequence $A=\{a_1,a_2,\cdots,a_n\}$ of length $n$. For a subsequence of $A$, $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$ ($0\le m\le n$, $1\le b_1<b_2<\cdots<b_m\le n$, same below), we call $B$ an excellent subsequence of $A$ if and only if the bitwise AND of any two different elements is $0$, that is: for all $1\le i<j\le m$, it holds that $a_{b_i}~\mathrm{and}~a_{b_j}=0$, where $~\mathrm{and}~$ is the bitwise AND operation.

For the subsequence $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$, we define its value as $\varphi(1+\sum_{i=1}^m a_{b_i})$, where $\varphi(x)$ denotes the number of positive integers not greater than $x$ that are coprime to $x$.

Now please compute the sum of values of all excellent subsequences of $A$. Output the answer modulo $10^9+7$.

Input Format

The first line contains a positive integer $n$, denoting the length of the sequence.

The second line contains $n$ non-negative integers separated by spaces, denoting $a_1,a_2,\cdots,a_n$.

Output Format

Only one line with one integer, denoting the result of the answer modulo $10^9+7$.

4
1 2 2 3

12

Hint

Explanation for Sample 1

The valid subsequences are: $\emptyset$, $\{1\}$, $\{2\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,2\}$. Their values are $1$, $1$, $2$, $2$, $2$, $2$, $2$, respectively, and the total sum is $12$.

Constraints

• For $10\%$ of the testdata, it is guaranteed that $a_i\le 1$.
• For $30\%$ of the testdata, it is guaranteed that $a_i\le 1000$.
• For $60\%$ of the testdata, it is guaranteed that $a_i\le 30000$.
• There is another $10\%$ of the testdata where it is guaranteed that $n\le 20$.
• For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^6$ and $0\le a_i\le 2\times 10^5$.

Translated by ChatGPT 5