Excellent Subsequence Totient Sum

You are given a sequence \(A = \{a_1, a_2, \cdots, a_n\}\) of non-negative integers. A subsequence \(B = \{a_{b_1}, a_{b_2}, \cdots, a_{b_m}\}\) (where \(0 \le m \le n\) and \(1 \le b_1 < b_2 < \cdots < b_m \le n\)) is called an excellent subsequence if for every two different elements in \(B\), their bitwise AND is zero. That is, for every \(1 \le i < j \le m\):

[ a_{b_i} ;\mathrm{and}; a_{b_j} = 0 ]

For any subsequence \(B\), its value is defined as:

[ \varphi\Bigl(1 + \sum_{i=1}^{m} a_{b_i}\Bigr), ]

where \(\varphi(x)\) denotes Euler's totient function, i.e. the number of positive integers less than or equal to \(x\) that are coprime with \(x\).

Your task is to compute the sum of the values of all excellent subsequences of \(A\). Since the answer can be large, output it modulo \(10^9+7\). Note that the empty subsequence is considered an excellent subsequence, with value \(\varphi(1)=1\).

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le 20)\) representing the length of the sequence \(A\). The second line contains \(n\) non-negative integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer which is the sum of the values of all excellent subsequences modulo \(10^9+7\).

sample

3
1 2 3

8