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.
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1194F
   {
      static long MOD = 1000000007L;
      public static void main(String hi[]) throws Exception
      {
         long inv2 = power(2, MOD-2, MOD);
         fac = new long[200001];
         invfac = new long[200001];
         fac[0] = invfac[0] = 1L;
         for(int i=1; i <= 200000; i++)
            fac[i] = (fac[i-1]*i)%MOD;
         invfac[200000] = power(fac[200000], MOD-2, MOD);
         for(int i=199999; i >= 1; i--)
            invfac[i] = (invfac[i+1]*(i+1))%MOD;
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         long T = Long.parseLong(st.nextToken());
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken())+1;
         long res = 0L;
         long sum = 0L;
         long denom = 1L;
         int dex = 0;
         while(dex < N && sum+arr[dex] <= T)
         {
            sum += arr[dex++];
            denom = (denom*inv2)%MOD;
         }
         for(int ones=0; ones <= dex; ones++)
         {
            long temp = (comb(dex, ones)*denom)%MOD;
            long addend = (temp*dex)%MOD;
            if(dex < N && sum+arr[dex]-1 == T)
               addend = (addend*inv2)%MOD;
            res += addend;
            if(res >= MOD)
               res -= MOD;
            sum--;
            if(dex < N && sum+arr[dex] <= T)
            {
               sum += arr[dex++];
               denom = (denom*inv2)%MOD;
            }
         }
         System.out.println(res%MOD);
      }
      static long[] fac, invfac;
      public static long comb(int a, int b)
      {
         long res = (fac[a]*invfac[b])%MOD;
         return (res*invfac[a-b])%MOD;
      }
      public static long power(long x, long y, long p) 
      { 
         //0^0 = 1
         long res = 1L;      
         x = x%p;  
         while(y > 0) 
         { 
            if((y&1)==1) 
               res = (res*x)%p;
            y >>= 1;
            x = (x*x)%p;  
         } 
         return res; 
      } 
   }