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

public class CrosswordExpert {
    public static long MOD = 1000000007;
    public static int MAXN = 200005;
    public static long[] fact;
    public static long[] invfact;
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        long t = Long.parseLong(st.nextToken());
        fact = new long[MAXN];
        invfact = new long[MAXN];
        fact[0] = 1;
        invfact[0] = 1;
        for(int i = 1; i < MAXN; i++){
            fact[i] = (fact[i-1]*i)%MOD;
            invfact[i] = pow(fact[i], MOD-2, MOD);
        }
        long expVal = 0;
        long INV2 = pow(2, MOD-2, MOD);
        long mult = 1;
        long[] arr = new long[n];
        st = new StringTokenizer(f.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Long.parseLong(st.nextToken())+1;
        }
        long sum = 0;
        int ptr = 0;
        while(ptr < n && sum+arr[ptr] <= t){
            sum+=arr[ptr];
            ptr++;
            mult*=INV2;
            mult%=MOD;
        }
        for(int i = 0; i <= ptr; i++){
            long prob = (ncr(ptr, i)*mult)%MOD;
            long toAdd = (prob*ptr)%MOD;
            if(ptr != n && sum+arr[ptr]-1 == t) toAdd = (toAdd*INV2)%MOD;
            expVal+=toAdd;
            expVal%=MOD;
            sum--;
            if(ptr != n && sum+arr[ptr] <= t){
                sum+=arr[ptr];
                ptr++;
                mult*=INV2;
                mult%=MOD;
            }
        }
        out.println(expVal);
        out.close();


    }
    public static long ncr(int n, int r){
        if(n < r) return 0;
        if(r < 0) return 0;
        if(n < 0) return 0;
        return(((fact[n]*invfact[r])%MOD*invfact[n-r])%MOD);
    }
    public static long pow(long x, long y, long p){
        long res = 1;

        x = x % p;

        if (x == 0) return 0;

        while (y > 0)
        {
            if((y & 1)==1)
                res = (res * x) % p;

            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
}
