给定一个长度为 $n$ 的非负整数序列 $A=\{a_1,a_2,\cdots,a_n\}$，对于 $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 $,下同)，称 $B$ 是 $A$ 的优秀子序列当且仅当，其任意两个不同元素的按位与结果均为 $0$ ，即：$\forall 1\le i<j\le m$ ，满足：$a_{b_i}~\mathrm{and}~a_{b_j}=0$，其中 $~\mathrm{and}~$  是按位与运算。

对于子序列 $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$ ，我们定义其价值为 $\varphi(1+\sum_{i=1}^m a_{b_i})$ ，其中 $\varphi(x)$ 表示小等于 $x$ 的正整数中与 $x$ 互质的数的个数。
现在请你求出 $A$ 的所有优秀子序列的价值之和，答案对 $10^9$ 取模。

第一行一个正整数 $n$ 表示序列长度。
第二行 nn 个用空格分隔的非负整数，表示 $a_1,a_2,\cdots,a_n$ 。

仅一行一个整数，表示答案对 $10^9+7$ 取模的结果。

4
1 2 2 3

12