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。