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 $\frac{1}{2}$ he solves the crossword in exactly $t_i$ seconds, and with probability $\frac{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 = \sum \limits_{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 $\frac{P}{Q}$ with $Q > 0$. To give the answer, you should print $P \cdot Q^{-1} \bmod (10^9 + 7)$.


-----Input-----

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

The second line contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 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 \cdot Q^{-1} \bmod (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 $\frac{14}{8}$.

The answer for the second sample is equal to $\frac{17}{8}$.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin, stdout, exit

mod = 10**9 + 7

def modinv(x):
    return pow(x, mod-2, mod)

N = 2*10**5 + 10
facts = [1]*N
for i in range(1,N):
    facts[i] = facts[i-1] * i
    facts[i] %= mod

def binom(n, k):
    ans = modinv(facts[k]) * modinv(facts[n-k])
    ans %= mod
    ans *= facts[n]
    ans %= mod
    return ans

#print("Finished preprocess")

n, T = list(map(int, stdin.readline().split()))
ts = list(map(int, stdin.readline().split()))

ans = 0
total = sum(ts)
running = total
last_idx = n-1
while running > T:
    running -= ts[last_idx]
    last_idx -= 1
#print(last_idx+1)

last_bd = -1
last_sum = 0
idx = last_idx
while running + idx + 1 > T:
    bd = T - running
#    print("time remaining for", idx+1, "flips is", bd)
    cur_sum = last_sum + (binom(idx+1, last_bd) if last_bd >= 0 else 0)
    cur_sum *= modinv(2)
    cur_sum %= mod
    for fresh in range(last_bd+1, bd+1):
        cur_sum += binom(idx+1, fresh)
        cur_sum %= mod
 #   print("pr of", idx+1, "flips is", cur_sum, cur_sum / (2**(idx+1)))
    ans += cur_sum * modinv(pow(2, idx+1, mod))
    ans %= mod
    running -= ts[idx]
    last_bd = bd
    last_sum = cur_sum
    idx -= 1

#print(idx+1, "freebies")
ans += idx+1
ans %= mod
print(ans)


MOD = 10 ** 9 + 7
MAX = 5 * 10 ** 5
fac, ifac = [1] * MAX, [1] * MAX
for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
ifac[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(MAX - 2, 1, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % MOD
ipow2 = [1] * MAX
for i in range(1, MAX):
    ipow2[i] = ipow2[i - 1] * (MOD + 1) // 2 % MOD

choose = lambda n, k: fac[n] * ifac[k] % MOD * ifac[n - k] % MOD

n, t = map(int, input().split())
a = list(map(int, input().split()))

s = 0
p = [1] + [0] * (n + 1)
k = cur = 0
for i in range(n):
    s += a[i]
    if s > t: break
    if s + i + 1 <= t:
        p[i + 1] = 1
        continue
    if not cur:
        k = t - s
        for j in range(k + 1):
            cur += choose(i + 1, j)
        cur %= MOD
    else:
        cur = cur * 2 - choose(i, k)
    while k > t - s:
        cur -= choose(i + 1, k)
        k -= 1
    cur %= MOD
    p[i + 1] = cur * ipow2[i + 1] % MOD

print(sum((p[i] - p[i + 1]) * i % MOD for i in range(1, n + 1)) % MOD)

MOD = 10 ** 9 + 7
MAX = 5 * 10 ** 5
fac, ifac, ipow2 = [1] * MAX, [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    ifac[i] = pow(fac[i], MOD - 2,MOD)
    ipow2[i] = ipow2[i - 1] * (MOD + 1) // 2 % MOD

choose = lambda n, k: fac[n] * ifac[k] % MOD * ifac[n - k] % MOD

n, t = map(int, input().split())
a = list(map(int, input().split()))

s = 0
p = [1] + [0] * (n + 1)
k = cur = 0
for i in range(n):
    s += a[i]
    if s > t: break
    if s + i + 1 <= t:
        p[i + 1] = 1
        continue
    newk = t - s
    cur = cur * 2 - choose(i, k) if cur else sum(choose(i + 1, j) for j in range(newk + 1)) % MOD
    if newk < k:
        cur -= sum(choose(i + 1, x) for x in range(k, newk, -1))
    cur %= MOD
    p[i + 1] = cur * ipow2[i + 1] % MOD
    k = newk

print(sum((p[i] - p[i + 1]) * i % MOD for i in range(1, n + 1)) % MOD)

MOD = 10 ** 9 + 7
MAX = 5 * 10 ** 5
fac, ifac, ipow2 = [1] * MAX, [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    ifac[i] = pow(fac[i], MOD - 2, MOD)
    ipow2[i] = ipow2[i - 1] * (MOD + 1) // 2 % MOD

choose = lambda n, k: fac[n] * ifac[k] % MOD * ifac[n - k] % MOD

n, t = map(int, input().split())
a = list(map(int, input().split()))

s = 0
p = [1] + [0] * (n + 1)
k = cur = 0
for i in range(n):
    s += a[i]
    if s > t: break
    if s + i + 1 <= t:
        p[i + 1] = 1
        continue
    newk = t - s
    cur = cur * 2 - choose(i, k) if cur else sum(choose(i + 1, j) for j in range(newk + 1))
    if newk < k:
        cur -= sum(choose(i + 1, x) for x in range(k, newk, -1))
    cur %= MOD
    p[i + 1] = cur * ipow2[i + 1] % MOD
    k = newk

print(sum((p[i] - p[i + 1]) * i % MOD for i in range(1, n + 1)) % MOD)

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5 + 10
 
r     = [1] * MAX  
f     = [1] * MAX
rf    = [1] * MAX
rp2   = [1] * MAX 
 
for i in range(2, MAX):
    f[i]   = f[i - 1] * i % mod
    r[i]   = mod - (mod // i) * r[mod%i] % mod
    rf[i]  = rf[i-1] * r[i] % mod
    
for i in range(1, MAX):
    rp2[i] = rp2[i - 1] * (mod + 1) // 2 % mod
    
n, T = list(map(int, input().split()))
t    = list(map(int, input().split()))
t.append(10**14+1)    
 
S=0
E=0
for i in range(len(t)):
    cof = rp2[1] 
    
    for add in range(2):
        l_, r_ =  max(0, T-S-(t[i]-add)), min(i, T-S)
        
        for x in range(l_, r_+1):
            E = ( E + i * (f[i]*rf[x]*rf[i-x]) * rp2[i] * cof ) % mod    
    S   += t[i]   
    
print(E)