操作を一回行うと、選んだ銘柄の資産価値の分だけ全体の資産価値の合計が大きくなります。つまり、最も資産価値の高い銘柄を選び続けて \(K\) 回操作することが最適です。

答えは \(\sum S_i + (2^K-1)(\max S_i)\) となります。

\(2^K\) は繰り返し二乗法により \(\mathrm{O}(\log K)\) で求めることができ、全体で\(\mathrm{O}(N+\log K)\) で答えが求まります。

また、この問題では \(10^9+7\) で割った余りを求めたいので適宜割った余りを取ることにより、64bit整数型のみでの演算で計算できます。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;
static constexpr long long mod = 1000000007;
long long modpow(long long a, long long b, long long md) {
    long long res = 1;
    while (b) {
        if (b & 1) res *= a, res %= mod;
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return res;
}
int main() {
    long long n, k;
    cin >> n >> k;
    vector<long long> s(n);
    for (auto& e : s) cin >> e;
    long long ma = *max_element(s.begin(), s.end());
    long long sum = 0;
    sum += modpow(2, k, mod) * ma % mod;
    sum += mod - ma;
    sum %= mod;
    for (auto e : s) {
        sum += e;
        sum %= mod;
    }
    cout << sum << endl;
}