[NOI Online #3 提高组]优秀子序列(民间数据)

题目描述

给定一个长度为 $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+7$ 取模。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

4
1 2 2 3

输出样例 #1

12

说明

#### 样例 1 解释 符合条件的子序列有:$\emptyset$,$\{1\}$,$\{2\}$,$\{2\}$,$\{3\}$,$\{1,2\}$,$\{1,2\}$,它们价值依次为 $1$,$1$,$2$,$2$,$2$,$2$,$2$,总和为 $12$。 #### 数据规模与约定 - 对于 $10\%$ 的数据,保证 $a_i\le 1$。 - 对于 $30\%$ 的数据,保证 $a_i\le 1000$。 - 对于 $60\%$ 的数据,保证 $a_i\le 30000$。 - 另有 $10\%$ 的数据,保证 $n\le 20$。 - 对于 $100\%$ 的数据,保证 $1\le n\le 10^6$,$0\le a_i\le 2\times 10^5$。