题目描述

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

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

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

给你一个长度为 $n$ 的正整数可重集合 $A={a_1,a_2,\ldots,a_n}$。问你有多少个集合 $B={b_1,b_2,\ldots,b_k}$ 满足 $B \subseteq A$，且 $\gcd(b_1,b_2,\ldots,b_k)=\gcd(a_1,a_2,\ldots,a_n)$？

题意：有多少个序列 $A$ 的子集，满足子集的 $\gcd$ 等于序列 $A$ 的 $\gcd$。

由于答案可能很大，你只需要求出其对 $10^9+7$ 取模的结果即可。

输入格式

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

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

输出格式

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

4
2 4 3 2

7

样例 1 解释

给定的四个整数的 $\gcd=1$。符合条件的集合 $B$ 一共有 $7$ 个分别是：

• $\{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