Tarefa «Cálculo do produto máximo de uma subsequência com divisão em fatores primos»

Dada uma sequência de números inteiros a1, a2, ..., an. É necessário encontrar o produto máximo de uma subsequência (não necessariamente contínua) de comprimento k, onde k é dado. É permitido dividir os elementos em seus fatores primos, mas no máximo uma vez por elemento. Ou seja, para cada elemento pode-se pegá-lo por inteiro ou substituí-lo por um de seus fatores primos (se não for um número primo), e só então utilizá-lo no produto. Se o elemento for um número primo, ele só pode ser pego por inteiro ou descartado. É necessário exibir o maior produto possível módulo 10^9+7.