CF653G.Move by Prime

Pussycat Sonya has an array consisting of n positive integers. There are 2_n_ possible subsequences of the array. For each subsequence she counts the minimum number of operations to make all its elements equal. Each operation must be one of two:

• Choose some element of the subsequence and multiply it by some prime number.
• Choose some element of the subsequence and divide it by some prime number. The chosen element must be divisible by the chosen prime number.

What is the sum of minimum number of operations for all 2_n_ possible subsequences? Find and print this sum modulo 109 + 7.

小猫索尼娅有一个由 $n$ 个正整数组成的数组。该数组共有 $2^n$ 个可能的子序列。对于每个子序列，她计算使其所有元素相等所需的最少操作次数。每次操作必须是以下两种之一：

• 选择子序列中的某个元素，并将其乘以某个质数；
• 选择子序列中的某个元素，并将其除以某个质数（所选元素必须能被该质数整除）。

对全部 $2^n$ 个可能子序列的最少操作次数求和，结果对 $10^9 + 7$ 取模。请计算并输出该和。

The first line of the input contains a single integer n (1 ≤ n ≤ 300 000) — the size of the array.

The second line contains n integers _t_1, _t_2, ..., t__n (1 ≤ t__i ≤ 300 000) — elements of the array.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 300\,000$）—— 数组的大小。

第二行包含 $n$ 个整数 $t_1,\,t_2,\,...,\,t_n$（$1 \leq t_i \leq 300\,000$）—— 数组的元素。

Print the sum of minimum number of operation for all possible subsequences of the given array modulo 109 + 7.

输出对给定数组所有可能子序列所需的最少操作次数之和（对 $10^9 + 7$ 取模）。

In the first sample, there are 8 possible subsequences: (60, 60, 40), (60, 60), (60, 40), (60, 40), (60), (60), (40) and () (empty subsequence).

For a subsequence (60, 60, 40) we can make all elements equal by two operations — divide 40 by 2 to get 20, and then multiply 20 by 3 to get 60. It's impossible to achieve the goal using less operations and thus we add 2 to the answer.

There are two subsequences equal to (60, 40) and for each of them the also need to make at least 2 operations.

In each of other subsequences all numbers are already equal, so we need 0 operations for each of them. The sum is equal to 2 + 2 + 2 = 6.

在第一个样例中，共有 8 个可能的子序列：$(60,\,60,\,40)$、$(60,\,60)$、$(60,\,40)$、$(60,\,40)$、$(60)$、$(60)$、$(40)$ 和 $()$（空子序列）。

对于子序列 $(60,\,60,\,40)$，我们可以通过两次操作使所有元素相等：先将 $40$ 除以 $2$ 得到 $20$，再将 $20$ 乘以 $3$ 得到 $60$。无法用少于两次操作达成目标，因此向答案中加上 $2$。

有两个子序列等于 $(60,\,40)$，对每个这样的子序列也都至少需要 $2$ 次操作。

其余每个子序列中的所有数字已相等，因此对每个这样的子序列均需 $0$ 次操作。总和为 $2\,+\,2\,+\,2\,=\,6$。