G. Ход простым
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У кошечки Сони есть массив, состоящий из n целых положительных чисел. У этого массива есть 2n подпоследовательности. Для каждой подпоследовательности Соня вычисляет минимальное количество действий, которые необходимо совершить, чтобы сделать все элементы равными. Возможны следующие действия:

  • Выбрать один элемент подпоследовательности и умножить его на простое число;
  • Выбрать какой-нибудь элемент подпоследовательности и поделить его на простое число. При этом данный элемент должен обязательно делиться на выбранное простое число.

Чему равна сумма минимального количества необходимых операций по всем 2n подпоследовательностям? Найдите и выведите это значение по модулю 109 + 7.

Входные данные

В первой строке входных данных записано единственное число n (1 ≤ n ≤ 300 000) — длина массива.

Во второй строке записаны n целых чисел t1, t2, ..., tn (1 ≤ ti ≤ 300 000) — элементы массива.

Выходные данные

Выведите сумму минимального количества операций, необходимых, чтобы уравнять все элементы подпоследовательности по всем подпоследовательностям данного массива. Значение выводите по модулю 109 + 7.

Примеры
Входные данные
3
60 60 40
Выходные данные
6
Входные данные
4
1 2 3 4
Выходные данные
24
Примечание

В первом примере возможны 8 различных подпоследовательностей: (60, 60, 40), (60, 60), (60, 40), (60, 40), (60), (60), (40) и () (пустая подпоследовательность).

Все элементы подпоследовательности (60, 60, 40) можно сделать одинаковыми за два действия: сперва разделить 40 на 2 и получить 20, а затем умножить 20 на 3 и получить 60. За меньшее количество действий сделать все элементы равными невозможно.

Две подпоследовательности равны (60, 40), и для каждой из них придётся также сделать не меньше 2 операций.

В каждой из оставшихся подпоследовательностей все элементы и так уже равны, поэтому на них мы потратим 0 операций. Таким образом, ответ равен 2 + 2 + 2 = 6.