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.
/**
 * author: derrick20
 * created: 10/3/20 12:50 AM
 */

import java.io.*;

public class CrosswordExpertSimple implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new CrosswordExpertSimple(), ": )", 1 << 28).start();
    }

    public void run() {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        setupCombo((int) 2e5 + 1);
        int N = sc.nextInt();
        long T = sc.nextLong();
        long[] time = new long[N + 2];

        for (int i = 1; i <= N; i++) {
            time[i] = sc.nextLong();
        }
        time[N + 1] = T + 1;

        long EV = 0;
        long prefix = time[1];
        for (int puzzles = 1; puzzles <= N; puzzles++, prefix += time[puzzles]) {
            if (prefix + time[puzzles + 1] + puzzles < T || prefix > T) {
                // With the current number of puzzles, we can still
                // fit the next puzzle in, so this amount is impossible.
                continue;
            }
            for (int extra = 0; extra <= 1; extra++) {
                // KEY idea: prefix + ones <= T, but also T < prefix + next + ones + extra
                // the strict inequality ensures that it cannot fit. We can either put an extra
                // 1 there, or not, but that case still contributes to us being able to have
                // the full [puzzles] chunk
                // -> ones <= T - prefix,
                // -> ones > T - prefix - next - extra
                // also, we have the standard bounds 0 <= ones <= puzzles

                /*
                Intuition. We need enough to keep out the next one (potentially expanded by 1)
                So we need 1 more than the amount that would let it fit perfectly. We also can't
                go beyond the amount that would allow the current amount fit.
                The runtime perfectly works out because we only cover disjoint sets of positions
                that are bounded by N
                 */
                int minOnes = (int) Math.max(0, T - prefix - time[puzzles + 1] - extra + 1);
                if (minOnes > puzzles) continue; // not enough
                int maxOnes = (int) Math.max(0, Math.min(T - prefix, puzzles));
//                System.out.println("Puzzles = " + puzzles + " min = " + minOnes + ", max = " + maxOnes + " extra = " + extra);
                for (int ones = minOnes; ones <= maxOnes; ones++) {
                    EV = add(EV, mult(puzzles, mult(twoPowInv[puzzles + 1], choose(puzzles, ones))));
                }
            }
//            System.out.println("At puzzles = " + puzzles + " EV = " + EV);
        }
        out.println(EV);
        out.close();
    }

    // todo SET THE MOD
    static long mod = (long) 1e9 + 7;
    static long[] fact, invFact, twoPowInv;

    static void setupCombo(int MAX) {
        fact = new long[MAX + 1];
        invFact = new long[MAX + 1];
        twoPowInv = new long[MAX + 1];

        fact[0] = 1;
        invFact[0] = 1;
        twoPowInv[0] = 1;
        long twoInv = fastExpo(2, mod - 2);
        for (int i = 1; i <= MAX; i++) {
            fact[i] = ((long) i * fact[i - 1]) % mod;
            invFact[i] = inv(fact[i]);
            twoPowInv[i] = (twoInv * twoPowInv[i - 1]) % mod;
        }
    }

    static long mult(long a, long b) {
        return (a * b) % mod;
    }

    static long add(long a, long b) {
        long ans = a + b;
        if (ans >= mod) {
            ans -= mod;
        }
        return ans;
    }

    static long choose(int n, int k) {
        if (k > n) return 0; // this works in THIS PROBLEM
        long ans = (fact[n] * invFact[n - k]) % mod;
        return (ans * invFact[k]) % mod;
    }

    static long inv(long x) {
        return fastExpo(x, mod - 2);
    }

    static long fastExpo(long x, long k) {
        long ans = 1;
        long bit = x;
        while (k > 0) {
            if (k % 2 == 1) {
                ans = (bit * ans) % mod;
            }
            bit = (bit * bit) % mod;
            k /= 2;
        }
        return ans;
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }

    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }

    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}