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: VERY_HARD
Tags: Probability

Combinatorics

Amortized analysis

Number theory

Dynamic programming
Skill types: Dynamic programming

Amortized analysis

Starter code:

Solutions:
mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5 + 1
r = [1] * MAX
factorial = [1] * MAX
rfactorial = [1] * MAX
rp = [1] * MAX
for i in range(2, MAX):
	factorial[i] = i * factorial[i - 1] % mod
	r[i] = mod - mod // i * r[mod % i] % mod
	rfactorial[i] = rfactorial[i - 1] * r[i] % mod
for i in range(1, MAX):
	rp[i] = rp[i - 1] * (mod + 1) // 2 % mod
(n, T) = list(map(int, input().split()))
t = list(map(int, input().split()))
t.append(10 ** 10 + 1)
S = 0
EX = 0
for i in range(len(t)):
	cof = rp[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):
			EX = (EX + i * (factorial[i] * rfactorial[x] * rfactorial[i - x]) * rp[i] * cof) % mod
	S += t[i]
print(EX)


mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5 + 2
r = [1] * MAX
factorial = [1] * MAX
rfactorial = [1] * MAX
rp = [1] * MAX
for i in range(2, MAX):
	factorial[i] = i * factorial[i - 1] % mod
	r[i] = mod - mod // i * r[mod % i] % mod
	rfactorial[i] = rfactorial[i - 1] * r[i] % mod
for i in range(1, MAX):
	rp[i] = rp[i - 1] * (mod + 1) // 2 % mod
(n, T) = list(map(int, input().split()))
t = list(map(int, input().split()))
t.append(10 ** 10 + 1)

def Combination(n, k):
	return factorial[n] * rfactorial[k] * rfactorial[n - k]
S = 0
E = 0
for i in range(0, n + 1):
	sim = 0
	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):
			sim += Combination(i, x) * rp[i + 1]
	E = (E + i * sim) % mod
	S += t[i]
print(E)


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)


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
(n, T) = 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
last_bd = -1
last_sum = 0
idx = last_idx
while running + idx + 1 > T:
	bd = T - running
	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
	ans += cur_sum * modinv(pow(2, idx + 1, mod))
	ans %= mod
	running -= ts[idx]
	last_bd = bd
	last_sum = cur_sum
	idx -= 1
ans += idx + 1
ans %= mod
print(ans)


mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5 + 2
(n, T) = list(map(int, input().split()))
t = [0]
t += list(map(int, input().split()))
t += [MAX]
r = [1] * MAX
factorial = [1] * MAX
rfactorial = [1] * MAX
rp = [1] * MAX
sim = 0
sim_n = 0
sim_k = 0
E = 0
S = [t[0]] * len(t)
for i in range(1, len(t)):
	S[i] = S[i - 1] + t[i]
for i in range(2, MAX):
	factorial[i] = i * factorial[i - 1] % mod
	r[i] = mod - mod // i * r[mod % i] % mod
	rfactorial[i] = rfactorial[i - 1] * r[i] % mod
for i in range(1, MAX):
	rp[i] = rp[i - 1] * (mod + 1) // 2 % mod

def Combination(n, k):
	if n < k:
		return 0
	return factorial[n] * rfactorial[k] * rfactorial[n - k]

def simC(x):
	aux = 0
	mi = min(x, T - S[x])
	for i in range(0, mi + 1):
		aux += Combination(x, i) % mod
	return (x, mi, aux)

def next_simC(next_x):
	mi1 = min(next_x, T - S[next_x])
	aux_sim = 2 * sim % mod
	aux_sim = (aux_sim + Combination(sim_n, sim_k + 1)) % mod
	aux_sim_n = sim_n + 1
	aux_sim_k = sim_k + 1
	while aux_sim_k > mi1:
		aux_sim = (aux_sim - Combination(aux_sim_n, aux_sim_k)) % mod
		aux_sim_k -= 1
	return (aux_sim_n, aux_sim_k, aux_sim)
i = 1
while i <= n and S[i] + i <= T:
	i += 1
	E += 1
if i <= n:
	(sim_n, sim_k, sim) = simC(i)
	for x in range(i, n + 1):
		E = (E + rp[x] * sim) % mod
		if T - S[x + 1] < 0:
			break
		(sim_n, sim_k, sim) = next_simC(x + 1)
print(E)


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)