#include <bits/stdc++.h>
using namespace std;
template <typename float_t>
struct complex {
  float_t x, y;
  complex<float_t>(float_t _x = 0, float_t _y = 0) : x(_x), y(_y) {}
  float_t real() const { return x; }
  void real(float_t _x) { x = _x; }
  float_t imag() const { return y; }
  void imag(float_t _y) { y = _y; }
  complex<float_t> &operator+=(const complex<float_t> &other) {
    x += other.x;
    y += other.y;
    return *this;
  }
  complex<float_t> &operator-=(const complex<float_t> &other) {
    x -= other.x;
    y -= other.y;
    return *this;
  }
  complex<float_t> operator+(const complex<float_t> &other) const {
    return complex<float_t>(*this) += other;
  }
  complex<float_t> operator-(const complex<float_t> &other) const {
    return complex<float_t>(*this) -= other;
  }
  complex<float_t> operator*(const complex<float_t> &other) const {
    return {x * other.x - y * other.y, x * other.y + other.x * y};
  }
};
template <typename float_t>
complex<float_t> conj(const complex<float_t> &c) {
  return {c.x, -c.y};
}
template <typename float_t>
complex<float_t> polar(float_t magnitude, float_t angle) {
  return {magnitude * cos(angle), magnitude * sin(angle)};
}
template <typename float_t>
ostream &operator<<(ostream &stream, const complex<float_t> &c) {
  return stream << '(' << c.x << ", " << c.y << ')';
}
namespace FFT {
const double ONE = 1;
const double PI = acos(-ONE);
vector<complex<double>> roots;
vector<long long> bit_reverse;
bool is_power_of_two(long long n) { return (n & (n - 1)) == 0; }
long long round_up_power_two(long long n) {
  assert(n > 0);
  while (n & (n - 1)) n = (n | (n - 1)) + 1;
  return n;
}
long long get_length(long long n) {
  assert(is_power_of_two(n));
  return __builtin_ctz(n);
}
template <typename complex_array>
void bit_reorder(long long n, complex_array &&values) {
  if ((long long)bit_reverse.size() != n) {
    bit_reverse.assign(n, 0);
    long long length = get_length(n);
    for (long long i = 0; i < n; i++)
      bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1));
  }
  for (long long i = 0; i < n; i++)
    if (i < bit_reverse[i]) swap(values[i], values[bit_reverse[i]]);
}
void prepare_roots(long long n) {
  if ((long long)roots.size() >= n) return;
  if (roots.empty()) roots = {{0, 0}, {1, 0}};
  long long length = get_length(roots.size());
  roots.resize(n);
  while (1 << length < n) {
    double min_angle = 2 * PI / (1 << (length + 1));
    for (long long i = 0; i < 1 << (length - 1); i++) {
      long long index = (1 << (length - 1)) + i;
      roots[2 * index] = roots[index];
      roots[2 * index + 1] = polar(ONE, min_angle * (2 * i + 1));
    }
    length++;
  }
}
template <typename complex_array>
void fft_recursive(long long n, complex_array &&values, long long depth = 0) {
  if (n <= 1) return;
  if (depth == 0) {
    assert(is_power_of_two(n));
    prepare_roots(n);
    bit_reorder(n, values);
  }
  n /= 2;
  fft_recursive(n, values, depth + 1);
  fft_recursive(n, values + n, depth + 1);
  for (long long i = 0; i < n; i++) {
    const complex<double> &even = values[i];
    complex<double> odd = values[n + i] * roots[n + i];
    values[n + i] = even - odd;
    values[i] = even + odd;
  }
}
template <typename complex_array>
void fft_iterative(long long N, complex_array &&values) {
  assert(is_power_of_two(N));
  prepare_roots(N);
  bit_reorder(N, values);
  for (long long n = 1; n < N; n *= 2)
    for (long long start = 0; start < N; start += 2 * n)
      for (long long i = 0; i < n; i++) {
        const complex<double> &even = values[start + i];
        complex<double> odd = values[start + n + i] * roots[n + i];
        values[start + n + i] = even - odd;
        values[start + i] = even + odd;
      }
}
inline complex<double> extract(long long N,
                               const vector<complex<double>> &values,
                               long long index, long long side) {
  if (side == -1) {
    long long other = (N - index) & (N - 1);
    return (conj(values[other] * values[other]) -
            values[index] * values[index]) *
           complex<double>(0, 0.25);
  }
  long long other = (N - index) & (N - 1);
  long long sign = side == 0 ? +1 : -1;
  complex<double> multiplier =
      side == 0 ? complex<double>(0.5, 0) : complex<double>(0, -0.5);
  return multiplier *
         complex<double>(values[index].real() + values[other].real() * sign,
                         values[index].imag() - values[other].imag() * sign);
}
void invert_fft(long long N, vector<complex<double>> &values) {
  assert(N >= 2);
  for (long long i = 0; i < N; i++) values[i] = conj(values[i]) * (ONE / N);
  for (long long i = 0; i < N / 2; i++) {
    complex<double> first = values[i] + values[N / 2 + i];
    complex<double> second = (values[i] - values[N / 2 + i]) * roots[N / 2 + i];
    values[i] = first + second * complex<double>(0, 1);
  }
  fft_recursive(N / 2, values.begin());
  for (long long i = N - 1; i >= 0; i--)
    values[i] = i % 2 == 0 ? values[i / 2].real() : values[i / 2].imag();
}
const long long FFT_CUTOFF = 150;
const double SPLIT_CUTOFF = 2e15;
const long long SPLIT_BASE = 1 << 15;
template <typename T_out, typename T_in>
vector<T_out> square(const vector<T_in> &input) {
  long long n = input.size();
  if (n < 1.5 * FFT_CUTOFF) {
    vector<T_out> result(2 * n - 1);
    for (long long i = 0; i < n; i++) {
      result[2 * i] += (T_out)input[i] * input[i];
      for (long long j = i + 1; j < n; j++)
        result[i + j] += (T_out)2 * input[i] * input[j];
    }
    return result;
  }
  long long N = round_up_power_two(n);
  assert(N >= 2);
  prepare_roots(2 * N);
  vector<complex<double>> values(N, 0);
  for (long long i = 0; i < n; i += 2)
    values[i / 2] = complex<double>(input[i], i + 1 < n ? input[i + 1] : 0);
  fft_iterative(N, values.begin());
  for (long long i = 0; i <= N / 2; i++) {
    long long j = (N - i) & (N - 1);
    complex<double> even = extract(N, values, i, 0);
    complex<double> odd = extract(N, values, i, 1);
    complex<double> aux = even * even + odd * odd * roots[N + i] * roots[N + i];
    complex<double> tmp = even * odd;
    values[i] = aux - complex<double>(0, 2) * tmp;
    values[j] = conj(aux) - complex<double>(0, 2) * conj(tmp);
  }
  for (long long i = 0; i < N; i++) values[i] = conj(values[i]) * (ONE / N);
  fft_recursive(N, values.begin());
  vector<T_out> result(2 * n - 1);
  for (long long i = 0; i < (long long)result.size(); i++) {
    double value = i % 2 == 0 ? values[i / 2].real() : values[i / 2].imag();
    result[i] = is_integral<T_out>::value ? round(value) : value;
  }
  return result;
}
template <typename T_out, typename T_in>
vector<T_out> multiply(const vector<T_in> &left, const vector<T_in> &right) {
  if (left == right) return square<T_out>(left);
  long long n = left.size();
  long long m = right.size();
  if (min(n, m) < FFT_CUTOFF) {
    vector<T_out> result(n + m - 1);
    for (long long i = 0; i < n; i++)
      for (long long j = 0; j < m; j++)
        result[i + j] += (T_out)left[i] * right[j];
    return result;
  }
  long long N = round_up_power_two(n + m - 1);
  vector<complex<double>> values(N, 0);
  for (long long i = 0; i < n; i++) values[i].real(left[i]);
  for (long long i = 0; i < m; i++) values[i].imag(right[i]);
  fft_iterative(N, values.begin());
  for (long long i = 0; i <= N / 2; i++) {
    long long j = (N - i) & (N - 1);
    complex<double> product_i = extract(N, values, i, -1);
    values[i] = product_i;
    values[j] = conj(product_i);
  }
  invert_fft(N, values);
  vector<T_out> result(n + m - 1);
  for (long long i = 0; i < (long long)result.size(); i++)
    result[i] =
        is_integral<T_out>::value ? round(values[i].real()) : values[i].real();
  return result;
}
template <typename T>
vector<T> mod_multiply(const vector<T> &left, const vector<T> &right, T mod,
                       bool split = false) {
  long long n = left.size();
  long long m = right.size();
  for (long long i = 0; i < n; i++) assert(0 <= left[i] && left[i] < mod);
  for (long long i = 0; i < m; i++) assert(0 <= right[i] && right[i] < mod);
  if (min(n, m) < (split ? 2 : 1) * FFT_CUTOFF) {
    const uint64_t ULL_BOUND =
        numeric_limits<uint64_t>::max() - (uint64_t)mod * mod;
    vector<uint64_t> result(n + m - 1);
    for (long long i = 0; i < n; i++)
      for (long long j = 0; j < m; j++) {
        result[i + j] += (uint64_t)left[i] * right[j];
        if (result[i + j] > ULL_BOUND) result[i + j] %= mod;
      }
    for (long long i = 0; i < (long long)result.size(); i++)
      if (result[i] >= (uint64_t)mod) result[i] %= mod;
    return vector<T>(result.begin(), result.end());
  }
  if (!split) {
    const vector<uint64_t> &product = multiply<uint64_t>(left, right);
    vector<T> result(n + m - 1);
    for (long long i = 0; i < (long long)result.size(); i++)
      result[i] = product[i] % mod;
    return result;
  }
  long long N = round_up_power_two(n + m - 1);
  vector<complex<double>> left_fft(N, 0), right_fft(N, 0);
  for (long long i = 0; i < n; i++) {
    left_fft[i].real(left[i] % SPLIT_BASE);
    left_fft[i].imag(left[i] / SPLIT_BASE);
  }
  fft_iterative(N, left_fft.begin());
  if (left == right) {
    copy(left_fft.begin(), left_fft.end(), right_fft.begin());
  } else {
    for (long long i = 0; i < m; i++) {
      right_fft[i].real(right[i] % SPLIT_BASE);
      right_fft[i].imag(right[i] / SPLIT_BASE);
    }
    fft_iterative(N, right_fft.begin());
  }
  vector<complex<double>> product(N);
  vector<T> result(n + m - 1);
  for (long long exponent = 0; exponent <= 2; exponent++) {
    uint64_t multiplier = 1;
    for (long long k = 0; k < exponent; k++)
      multiplier = multiplier * SPLIT_BASE % mod;
    fill(product.begin(), product.end(), 0);
    for (long long x = 0; x < 2; x++)
      for (long long y = 0; y < 2; y++)
        if (x + y == exponent)
          for (long long i = 0; i < N; i++)
            product[i] +=
                extract(N, left_fft, i, x) * extract(N, right_fft, i, y);
    invert_fft(N, product);
    for (long long i = 0; i < (long long)result.size(); i++) {
      uint64_t value = round(product[i].real());
      result[i] = (result[i] + value % mod * multiplier) % mod;
    }
  }
  return result;
}
}  // namespace FFT
const long long MOD = 1000000007;
long long n, k;
void find_prod(vector<long long> &ans, long long lo, long long hi,
               vector<long long> &a) {
  if (lo == hi) {
    for (long long i = 0; i <= a[lo]; i++) ans.push_back(1);
    return;
  }
  long long mid = (lo + hi) / 2;
  vector<long long> ans1, ans2;
  find_prod(ans1, lo, mid, a);
  find_prod(ans2, mid + 1, hi, a);
  vector<long long> tmp = FFT::mod_multiply(ans1, ans2, MOD, true);
  for (long long i = 0; i <= k; i++) ans.push_back(tmp[i]);
}
int32_t main() {
  cin >> n >> k;
  vector<long long> a(n);
  for (long long i = 0; i < n; i++) cin >> a[i];
  vector<long long> ans;
  find_prod(ans, 0, n - 1, a);
  long long val = 0;
  cout << ans[k] << "\n";
}
