该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

乘积

题目描述

黑大帅 有一个长度为 $n$ 的正整数数组$a_1,a_2,\dots,a_n$。

他最多可以进行 $k$ 次操作。每次操作按照以下方式进行：

1. 选择两个不同的位置 $i,j$，满足 $1\le i<j\le n$；

2. 选择两个正整数 $x,y$，满足

   $x\times y=a_i\times a_j$；

3. 将 $a_i$ 修改为 $x$，将 $a_j$ 修改为 $y$。

也就是说，每次操作可以在保持所选两个元素乘积不变的前提下，重新分配它们的值。

同一个位置可以参与多次操作。

黑大帅 可以进行少于 $k$ 次操作，也可以恰好进行 $k$ 次操作。他希望所有操作结束后，数组中所有元素之和尽可能大。

请你求出能够得到的最大数组元素和。

由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个整数 $n,k$，分别表示数组长度和最多可以进行的操作次数。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示初始数组。

输出格式

输出一行一个整数，表示最大数组元素和对 $10^9+7$ 取模后的结果。

样例输入 #1

5 2
1 2 3 4 5

样例输出 #1

65

样例解释1

第一次操作后，数组变为 $[1,2,12,1,5]$。

第二次操作，数组变为 $[1,2,60,1,1]$。

数据范围与约定

对于 $100\%$ 的数据，保证：$1\le k<n\le10^5$,$1\le a_i\le10^5$；

• 每次操作中选择的 $x,y$ 均为正整数。

• 特殊性质 A：保证 $k=1$。
• 特殊性质 B：保证所有 $a_i$ 均相等。
• 特殊性质 C：保证 $a_1\le a_2\le\cdots\le a_n$。