Today Adilbek is taking his probability theory test. Unfortunately, when Adilbek arrived at the university, there had already been a long queue of students wanting to take the same test. Adilbek has estimated that he will be able to start the test only T seconds after coming. 

Fortunately, Adilbek can spend time without revising any boring theorems or formulas. He has an app on this smartphone which contains n Japanese crosswords to solve. Adilbek has decided to solve them all one by one in the order they are listed in the app, without skipping any crossword. For each crossword, a number t_i is given that represents the time it takes an average crossword expert to solve this crossword (the time is given in seconds).

Adilbek is a true crossword expert, but, unfortunately, he is sometimes unlucky in choosing the way to solve the crossword. So, it takes him either t_i seconds or t_i + 1 seconds to solve the i-th crossword, equiprobably (with probability 1/2 he solves the crossword in exactly t_i seconds, and with probability 1/2 he has to spend an additional second to finish the crossword). All these events are independent.

After T seconds pass (or after solving the last crossword, if he manages to do it in less than T seconds), Adilbek closes the app (if he finishes some crossword at the same moment, that crossword is considered solved; otherwise Adilbek does not finish solving the current crossword at all). He thinks it would be an interesting probability theory problem to calculate E — the expected number of crosswords he will be able to solve completely. Can you calculate it? 

Recall that the expected value of a discrete random variable is the probability-weighted average of all possible values — in this problem it means that the expected value of the number of solved crosswords can be calculated as E = ∑ _{i = 0}^{n} i p_i, where p_i is the probability that Adilbek will solve exactly i crosswords. 

We can represent E as rational fraction P/Q with Q > 0. To give the answer, you should print P ⋅ Q^{-1} mod (10^9 + 7).

Input

The first line contains two integers n and T (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ T ≤ 2 ⋅ 10^{14}) — the number of crosswords and the time Adilbek has to spend, respectively.

The second line contains n integers t_1, t_2, ..., t_n (1 ≤ t_i ≤ 10^9), where t_i is the time it takes a crossword expert to solve the i-th crossword.

Note that Adilbek solves the crosswords in the order they are given in the input without skipping any of them.

Output

Print one integer — the expected value of the number of crosswords Adilbek solves in T seconds, expressed in the form of P ⋅ Q^{-1} mod (10^9 + 7).

Examples

Input


3 5
2 2 2


Output


750000007


Input


3 5
2 1 2


Output


125000003

Note

The answer for the first sample is equal to 14/8.

The answer for the second sample is equal to 17/8.
#include <bits/stdc++.h>
using lint = long long;
template <int MOD>
struct ModInt {
  using lint = long long;
  using mint = ModInt<MOD>;
  int val;
  ModInt(lint v = 0) : val(v % MOD) {
    if (val < 0) val += MOD;
  };
  ModInt& operator=(const ModInt& x) {
    if (this != &x) {
      this->val = x.val;
    }
    return *this;
  }
  ModInt operator+() const { return ModInt(val); }
  ModInt operator-() const { return ModInt(MOD - val); }
  ModInt operator~() const {
    int s = val, t = MOD;
    mint sx = 1, sy = 0, tx = 0, ty = 1;
    while (s % t != 0) {
      int div = s / t;
      s -= t * div;
      sx -= tx * div;
      sy -= ty * div;
      std::swap(s, t);
      std::swap(sx, tx);
      std::swap(sy, ty);
    }
    return mint(tx);
  }
  ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
  ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
  ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
  ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
  ModInt& operator+=(const ModInt& x) {
    if ((val += x.val) >= MOD) val -= MOD;
    return *this;
  }
  ModInt& operator-=(const ModInt& x) {
    if ((val -= x.val) < 0) val += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& x) {
    val = lint(val) * x.val % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& x) { return *this *= ~x; }
  bool operator==(const ModInt& b) const { return val == b.val; }
  bool operator!=(const ModInt& b) const { return val != b.val; }
  friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept {
    return os << x.val;
  }
};
constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;
template <int MOD>
class Combination {
  using mint = ModInt<MOD>;

 private:
  int MAX_V;
  std::vector<mint> f, invf;

 public:
  explicit Combination(int N) : MAX_V(N), f(MAX_V + 1), invf(MAX_V + 1) {
    f[0] = 1;
    for (int i = 1; i <= MAX_V; ++i) {
      f[i] = f[i - 1] * i;
    }
    invf[MAX_V] = ~f[MAX_V];
    for (int i = MAX_V - 1; i >= 0; --i) {
      invf[i] = invf[i + 1] * (i + 1);
    }
  }
  mint fact(int n) const { return f[n]; }
  mint invfact(int n) const { return invf[n]; }
  mint perm(int a, int b) const { return a < b ? mint(0) : f[a] * invf[a - b]; }
  mint comb(int a, int b) const {
    return a < b ? mint(0) : f[a] * invf[a - b] * invf[b];
  }
};
const Combination<MOD> C(1000000);
template <class T, class Int>
T ipow(T b, Int n) {
  T ret = 1;
  while (n > 0) {
    if (n & 1) ret *= b;
    n >>= 1;
    b *= b;
  }
  return ret;
}
int main() {
  int n;
  lint m;
  std::cin >> n >> m;
  mint ans = 0, sum = 1;
  int mprev = 0;
  bool less = false;
  for (int k = 1; k <= n; ++k) {
    lint t;
    std::cin >> t;
    m -= t;
    if (m < 0) {
      sum = 0;
    } else if (less) {
      while (mprev > m) {
        sum -= C.comb(k - 1, mprev) / ipow(mint(2), k - 1);
        --mprev;
      }
      sum -= C.comb(k - 1, mprev) / ipow(mint(2), k);
    } else if (m < k) {
      less = true;
      sum = 0;
      for (int i = 0; i <= m; ++i) {
        sum += C.comb(k, i);
      }
      sum /= ipow(mint(2), k);
      mprev = m;
    }
    ans += sum;
  }
  std::cout << ans << std::endl;
  return 0;
}
