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.*;
import java.util.*;

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

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

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

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

        int MAX = (int) 2e5; // todo change this!
        fact = new long[MAX + 1];
        invFact = new long[MAX + 1];
        long[] 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;
        }
        long ways = 0;
        int minOnes = 0;
        int maxOnes = (int) Math.min(puzzles, T - prefix[puzzles]);
        for (int ct = minOnes; ct <= maxOnes; ct++) {
            ways = (ways + choose(puzzles, ct)) % mod;
        }

        long EV = mult(puzzles, mult(ways, twoPowInv[puzzles]));
        puzzles--;
        while (puzzles >= 1) {
            if (prefix[puzzles + 1] + puzzles < T) {
                // With the current number of puzzles, we can still
                // fit the next puzzle in, so this amount is impossible.
                break;
            }
            // Otherwise, it's possible
            minOnes = (int) Math.min(T - prefix[puzzles + 1], puzzles);
            maxOnes = (int) Math.min(T - prefix[puzzles], puzzles);
            long waysReg = 0;
//            System.out.println("Puzzles = " + puzzles + " min = " + minOnes + " max = " + maxOnes);
            for (int ct = minOnes + 1; ct <= maxOnes; ct++) {
                waysReg = add(waysReg, choose(puzzles, ct));
            }
            long waysExtra = choose(puzzles, minOnes);
            long contrib = add(mult(waysReg, twoPowInv[puzzles]), mult(waysExtra, twoPowInv[puzzles + 1]));
            contrib = mult(puzzles, contrib);
            EV = add(EV, contrib);
            puzzles--;
        }
        out.println(EV);
        out.close();
    }

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

    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();
    }
}