Задача «Вычисление максимального произведения подпоследовательности с делением на простые множители»

Дана последовательность целых чисел a1, a2, ..., an. Необходимо найти максимальное произведение подпоследовательности (не обязательно непрерывной) длины k, где k задано. При этом разрешается делить элементы на их простые множители, но не более одного раза на элемент. То есть, для каждого элемента можно либо взять его целиком, либо заменить на один из его простых множителей (если он не является простым числом), и только после этого использовать в произведении. Если элемент является простым числом, его можно только взять целиком или не брать. Требуется вывести максимально возможное произведение по модулю 10^9+7.