Tâche «Calcul du produit maximal d'une sous-séquence avec division en facteurs premiers»

Étant donné une séquence d'entiers a1, a2, ..., an. Il faut trouver le produit maximal d'une sous-séquence (pas nécessairement continue) de longueur k, où k est donné. Il est permis de diviser les éléments en leurs facteurs premiers, mais pas plus d'une fois par élément. C'est-à-dire que pour chaque élément, on peut soit le prendre entièrement, soit le remplacer par l'un de ses facteurs premiers (s'il n'est pas un nombre premier), et seulement ensuite l'utiliser dans le produit. Si l'élément est un nombre premier, on peut seulement le prendre entièrement ou ne pas le prendre. Il faut afficher le produit maximal possible modulo 10^9+7.