小慕有一个长度为n的数组，她最多可以进行k次操作，每次操作如下： 1. 选择两个整数i, j，1 <= i < j <= n 2. 选择两个整数x, y，使得xy = aiaj 3. 将ai替换为x，将aj替换为y 她希望最多进行k次操作之后，最后数组中的元素的总和尽可能大。
提示：带虚线的词点一下有通俗解释。
输入描述
一行两个整数n, k，表示数组的长度和操作的次数。 一行n个整数 a1,a2,...,an，表示数组的元素。 1 <= k < n <= 10^5 1 <= ai <= 10^5
输出描述
输出一个整数，表示最后数组中的元素的总和的最大值，由于答案可能很大，你只需要输出答案对10^9+7取模的结果。
示例
示例 1
输入
5 2 1 2 3 4 5
输出
65
时间限制 1000 ms · 内存限制 128 MB