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

题目描述

赵襄子行车出游，至桥头时座下骏马忽然惊立长嘶。襄子心中一凛，叹道：“此必豫让伏于此处！”果然，侍卫搜桥，见豫让匿身暗处，持刃待发。多年隐忍、数次试探，终于到了生死一刻。

正如刺杀之谋需层层铺垫、步步筛选，真正的目标往往隐藏在众多选择之中。本题中，我们同样需要从整体中找出那些“本质一致”的子集。

在此问题中，假设有若干个数 $x_1,x_2,\dots,x_m$，那么 $\gcd(x_1,x_2,\dots,x_m)$ 表示这些数的最大公约数。

给你一个长度为 $n$ 的正整数可重集合 $A=\{a_1,a_2,\dots,a_n\}$。问你有多少个集合 $B=\{b_1,b_2,\dots,b_k\}$ 满足 $B \subseteq A$，且 $\gcd(b_1,b_2,\dots,b_k)=\gcd(a_1,a_2,\dots,a_n)$？由于答案可能很大，你只需要求出其对 $10^9+7$ 取模的结果即可。

输入格式

第一行一个整数 $n$ ($1 \le n \le 10^6$)。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ($1 \le a_i \le 10^6$)。

输出格式

一行一个整数，表示答案。

4
2 4 3 2

7

解释 #1

注意，题面给出的是可重集，即数值可以重复。假设可重集合 $\{2,2\}$，他有三个非空子集：$\{2\},\{2\},\{2,2\}$。

对于样例 $1$，符合条件的集合有：$\{2,4,3,2\}$、$\{2,3\}$、$\{4,3\}$、$\{2,4,3\}$、$\{3,2\}$、$\{2,3,2\}$、$\{4,3,2\}$。

10
2 2 4 4 2 2 6 8 6 8

1005