题目内容

你面前有一排 $n$ 个能量模块，第 $i$ 个模块的初始能量值为正整数 $a_i$。一次调谐操作可以选择两个不同的模块，将它们的能量值替换为两个正整数 $x$ 和 $y$，使得替换前后这两个模块能量值的乘积不变，即 $x \times y = a_i \times a_j$。你最多可以进行 $m$ 次调谐操作，目标是让所有模块的能量总和尽可能大。请你计算这个最大可能的总和，并对 $10^9+7$ 取模后输出。约束：$1 \le m < n \le 100000$，$1 \le a_i \le 100000$。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示能量模块的数量和最多可执行的调谐操作次数；第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个模块的初始能量值。

输出描述

输出一个整数，表示经过至多 $m$ 次调谐操作后所有模块能量总和的最大值对 $10^9+7$ 取模的结果。

样例1