1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <cstdlib>
 7 #include <string>
 8 #include <vector>
 9 #include <set>
10 #include <map>
11 #include <stack>
12 #include <queue>
13 using namespace std;
14 const int INF = 0x7fffffff;
15 const int MS = 100005;
16 const double EXP = 1e-8;
17 const int mod = 10000007;
18 typedef long long LL;
19 int a[MS];
20 int n, k;
21 struct Matrix
22 {
23     LL matrix[3][3];
24     Matrix()
25     {
26         memset(matrix, 0, sizeof(matrix));
27     }
28     Matrix operator *(const Matrix &b)const
29     {
30         Matrix x;
31         for (int i = 0; i < 3; i++)
32             for (int j = 0; j < 3; j++)
33                 for (int k = 0; k < 3; k++)
34                     x.matrix[i][j] = ((x.matrix[i][j] + matrix[i][k] * b.matrix[k][j]) % mod) % mod;
35         return x;
36     }
37 };
38 void solve()
39 {
40     sort(a, a + n);
41     LL sum = 0;
42     LL s, t;
43     for (int i = 0; i < n; i++)
44         sum += a[i];
45     s = static_cast<LL>(a[n - 2]);
46     t = static_cast<LL>(a[n - 1]);
47     Matrix m1, m2, ans;
48     m1.matrix[0][1] = m1.matrix[0][0] = m1.matrix[0][2] = 1;
49     m1.matrix[1][1] = m1.matrix[1][2] = 1;
50     m1.matrix[2][1] = 1;
51     ans.matrix[0][0] = ans.matrix[1][1] = ans.matrix[2][2] = 1;
52     while (k)
53     {
54         if (k & 1)
55             ans = ans*m1;
56         k >>= 1;
57         m1 = m1*m1;
58     }
59 
60     m2.matrix[0][0] = sum;
61     m2.matrix[1][0] = t;
62     m2.matrix[2][0] = s;
63     ans = ans*m2;
64     cout << ans.matrix[0][0] % mod << endl;
65     return;
66 }
67 int main()
68 {
69     while (cin >> n >> k)
70     {
71         for (int i = 0; i < n; i++)
72             cin >> a[i];
73         solve();
74     }
75     return 0;
76 }