#include <bits/stdc++.h>
#include <set>

#define ll long long
using namespace std;

ll mxN = 1000000007;

struct def {
    vector<int> set;
    int k;

    def(int k) {
        this -> k = k;
    }
};

ll mod(ll x, ll y) {
    return ((x % y) + y) % y;
}

void allSubs(vector<def>& sets, ll arr[], int ref, int k) {
    def *s = new def(k);
    for (int i = 0; i < ref; i++) {
        s -> set.push_back(arr[i]);
        sets.push_back(*s);

        for (int j = i + 1; j < ref; j++) {
            s -> set.push_back(arr[j]);
            sets.push_back(*s);
        }

        s -> set.clear();
    }
}

ll sum(ll arr[], int n, int k) {
    vector<def> d;

    k = k - 1;

    // The sum of all of the subsets
    ll res = 0;

    allSubs(d, arr, n, k);

    for (const def& each : d) {
        vector<int> set = each.set;

        if (set.size() == 1) {
            res = mod(res, mxN) + mod(set[0], mxN);
        } else if (set.size() == 2) {
            res = mod(res, mxN) + mod((set[0] + set[1]) * (k + 1), mxN);
        } else if (each.k == 0) {
            for (int &i : set) {
                res = mod(res, mxN) + mod(i, mxN);
            }
        } else {
            res = mod(res, mxN) + mod(sum(arr, set.size(), k), mxN);
        }
    }


    return res;
}


int main() {
    int n, k;
    scanf("%d%d", &n, &k);

    ll arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
    }

    ll res = 0;
    if (!k) {
        for (int i = 0; i < n; i++) {
            res = mod(res, mxN) + mod(arr[i], mxN);
        }

        cout << res % mxN;
    } else {
        vector<def> sets;
        cout << sum(arr, n, k);
    }

    return 0;
}