← 返回题目列表

Codeforces · 653/G

G. 按素数移动

中文机器翻译题面 查看原题

Pussycat Sonya 有一个由 n 个正整数组成的数组。该数组有 2n 个可能的子序列。对于每个子序列,她计算使其所有元素相等的最小操作数。每个操作必须是以下两个操作之一:

- 选择子序列的某个元素并将其乘以某个素数。
- 选择子序列的某个元素并将其除以某个素数。所选元素必须能被所选质数整除。

所有 2n 个可能的子序列的最小操作次数之和是多少?找到并打印这个模 109 + 7 的总和。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 300 000) — 数组的大小。

第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 300 000) — 数组的元素。

输出

打印给定数组的所有可能子序列模 109 + 7 的最小运算次数之和。

示例

输入 #1

3
60 60 40

输出 #1

6

输入 #2

4
1 2 3 4

输出 #2

24

注意

在第一个样本中,有 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。