У кошечки Сони есть массив, состоящий из n целых положительных чисел. У этого массива есть 2n подпоследовательности. Для каждой подпоследовательности Соня вычисляет минимальное количество действий, которые необходимо совершить, чтобы сделать все элементы равными. Возможны следующие действия:
- Выбрать один элемент подпоследовательности и умножить его на простое число;
- Выбрать какой-нибудь элемент подпоследовательности и поделить его на простое число. При этом данный элемент должен обязательно делиться на выбранное простое число.
Чему равна сумма минимального количества необходимых операций по всем 2n подпоследовательностям? Найдите и выведите это значение по модулю 109 + 7.
Выходные данные
Выведите сумму минимального количества операций, необходимых, чтобы уравнять все элементы подпоследовательности по всем подпоследовательностям данного массива. Значение выводите по модулю 109 + 7.
Примечание
В первом примере возможны 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.