该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石老板这几天一直郁郁寡欢，因为他无法解决如下数学题：

有 $n$ 个正整数 $a_i$，并令它们的积为 $S$，即 $S=a_1\times a_2 \times a_3\times \cdots\times a_n$。

这 $n$ 个正整数组成多重集合，一共有 $2^n-1$ 个真子集。对于一个包含 $m$ 个数的子集 $\lbrace a_{k_1},a_{k_2},\ldots,a_{k_m} \rbrace$，蕴含的势能为 $LCM(\frac{S}{a_{k_1}},\frac{S}{a_{k_2}},\ldots,\frac{S}{a_{k_m}})$，其中 $LCM$ 表示最小公倍数。

请求出所有真子集的势能之和，因为答案很大，只需求出答案对 $10^9+7$ 取模的结果。

输入格式

第一行一个整数 $n$，表示元素的个数。

第二行 $n$ 个正整数 $a_i$，用空格分隔。

输出格式

一个整数，表示势能之和对 $10^9+7$ 取模的结果。

样例输入

4
1 2 3 4

样例输出

302

样例解释

$S=1\times 2 \times 3 \times 4=24$，一共有 $15$ 个真子集。

总和为 $302$。

数据范围

对于 $30\%$ 的数据：$1\le n \le 10$，$1\le a_i \le 200$，$S\le 10^{18}$。

对于 $60\%$ 的数据：$1\le n \le 15$，$1\le a_i \le 10000$。

对于 $100\%$ 的数据：$1\le n \le 10^6$，$1\le a_i \le 10^6$。