Koa the Koala has a binary string $s$ of length $n$. Koa can perform no more than $n-1$ (possibly zero) operations of the following form:

In one operation Koa selects positions $i$ and $i+1$ for some $i$ with $1 \le i < |s|$ and sets $s_i$ to $max(s_i, s_{i+1})$. Then Koa deletes position $i+1$ from $s$ (after the removal, the remaining parts are concatenated).

Note that after every operation the length of $s$ decreases by $1$.

How many different binary strings can Koa obtain by doing no more than $n-1$ (possibly zero) operations modulo $10^9+7$ ($1000000007$)?


-----Input-----

The only line of input contains binary string $s$ ($1 \le |s| \le 10^6$). For all $i$ ($1 \le i \le |s|$) $s_i = 0$ or $s_i = 1$.


-----Output-----

On a single line print the answer to the problem modulo $10^9+7$ ($1000000007$).


-----Examples-----
Input
000

Output
3

Input
0101

Output
6

Input
0001111

Output
16

Input
00101100011100

Output
477



-----Note-----

In the first sample Koa can obtain binary strings: $0$, $00$ and $000$.

In the second sample Koa can obtain binary strings: $1$, $01$, $11$, $011$, $101$ and $0101$. For example:  to obtain $01$ from $0101$ Koa can operate as follows: $0101 \rightarrow 0(10)1 \rightarrow 011 \rightarrow 0(11) \rightarrow 01$.  to obtain $11$ from $0101$ Koa can operate as follows: $0101 \rightarrow (01)01 \rightarrow 101 \rightarrow 1(01) \rightarrow 11$. 

Parentheses denote the two positions Koa selected in each operation.

Difficulty: HARD

Starter code:

Solutions:
import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	MOD = int(1000000000.0 + 7)
	was = set()
	s = list(map(int, minp()))
	n = len(s)
	(first, last) = (None, None)
	for i in range(n):
		v = s[i]
		if v == 1:
			first = i
			break
	if first is None:
		print(n)
		return
	dp = [0] * n
	dp[first] = 1
	st = []
	stv = []
	r = 0
	i = first
	while i < n:
		j = i + 1
		while j < n and s[j] == 0:
			j += 1
		r = (r + dp[i]) % MOD
		if j == n:
			last = i
			break
		c = j - i - 1
		add = 0
		st.append(0)
		stv.append(dp[i])
		while len(st) > 0 and st[-1] <= c:
			v = st.pop()
			d = stv.pop()
			dp[j] = (dp[j] + d * (c - v + 1)) % MOD
			add += d
		if len(st) > 0 and st[-1] == c + 1:
			stv[-1] = (stv[-1] + add) % MOD
		else:
			st.append(c + 1)
			stv.append(add)
		i = j
	print(r * (first + 1) * (n - last) % MOD)
solve()


from itertools import groupby
s = input()
n = len(s)
s = [s[i] for i in range(n)]
mod = 10 ** 9 + 7
data = groupby(s)
data = [(key, len(list(group))) for (key, group) in data]
Start = 1
End = 1
if data[0][0] == '0':
	Start += data[0][1]
	data = data[1:]
if not data:
	print(Start - 1)
	exit()
if data[-1][0] == '0':
	End += data[-1][1]
	data.pop()
comp = [0] * len(data)
for i in range(len(data)):
	comp[i] = data[i][1]
n = len(comp)
if n == 1:
	print(comp[0] * Start * End)
	exit()
odd = [(comp[i], i // 2) for i in range(n) if i % 2 == 1]
N = len(odd)
ID = [-1] * n
stack = []
for i in range(N):
	while stack and stack[-1][0] < odd[i][0]:
		stack.pop()
	if stack:
		ID[2 * i + 1] = stack[-1][1]
	stack.append(odd[i])
dp = [0] * n
dp[0] = comp[0]
pre = [0] * n
for i in range(2, n, 2):
	id = ID[i - 1]
	if id == -1:
		res = comp[i - 1] * dp[i - 2]
		pre[i - 1] = res
	else:
		j = 2 * id + 1
		res = (comp[i - 1] * dp[i - 2] + pre[j] - comp[i - 1] * dp[j - 1]) % mod
		pre[i - 1] = res
	dp[i] = (comp[i] * res + dp[i - 2] + comp[i]) % mod
print(dp[-1] * Start * End % mod)


import sys
MOD = 1000000007

def red(x):
	return x if x < MOD else x - MOD
S = input()
n = len(S)
i = 0
while i < n and S[i] == '0':
	i += 1
if i == n:
	print(n)
	return
j = n
while j and S[j - 1] == '0':
	j -= 1
fac = (i + 1) * (n - j + 1)
S = S[i:j]
n = len(S)
count0 = [+(c == '0') for c in S]
for i in reversed(range(n - 1)):
	if count0[i]:
		count0[i] += count0[i + 1]
ways0 = 1
ways1 = 0
buckets = [0] * (n + 1)
buckets[0] = 1
for i in reversed(range(n)):
	if count0[i]:
		c = count0[i]
		ways0 = red(ways0 - buckets[c] + MOD)
		buckets[c] = ways1
		ways0 = red(ways0 + ways1)
	else:
		ways1 = red(ways1 + ways0)
print(ways1 * fac % MOD)


MOD = 1000000007

def main():
	s = input()
	n = len(s)
	zero = [0] * n
	for i in range(n):
		if s[i] == '0':
			zero[i] = zero[i - 1] + 1 if i else 1
	(nxt, dp) = ([0] * (n + 2), [0] * (n + 2))
	for i in range(n + 1):
		nxt[i] = n
	for i in range(n - 1, -1, -1):
		dp[i] = ((zero[i] <= zero[n - 1]) + dp[nxt[0]] + dp[nxt[zero[i] + 1]]) % MOD
		nxt[zero[i]] = i
	ans = n if nxt[0] >= n else dp[nxt[0]] * (nxt[0] + 1) % MOD
	print(ans)
main()


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
S = readline().strip().split('1')
if len(S) == 1:
	print(len(S[0]))
else:
	S = [len(s) + 1 for s in S]
	ans = S[0] * S[-1]
	S = S[1:-1]
	dp = [0] * (max(S) + 2)
	dp[0] = 1
	for ai in S:
		res = 0
		rz = 0
		for i in range(ai + 1):
			res = (res + dp[i]) % MOD
			rz = (rz + (ai - i) * dp[i]) % MOD
			dp[i] = 0
		dp[0] = rz
		dp[ai] = res
	aaa = 0
	for d in dp:
		aaa = (aaa + d) % MOD
	print(aaa * ans % MOD)


from itertools import groupby
s = input()
n = len(s)
s = [s[i] for i in range(n)]
mod = 10 ** 9 + 7
data = groupby(s)
data = [(key, len(list(group))) for (key, group) in data]
Start = 1
End = 1
if data[0][0] == '0':
	Start += data[0][1]
	data = data[1:]
if not data:
	print(Start - 1)
	return
if data[-1][0] == '0':
	End += data[-1][1]
	data.pop()
comp = [0] * len(data)
for i in range(len(data)):
	comp[i] = data[i][1]
n = len(comp)
if n == 1:
	print(comp[0] * Start * End)
	return
odd = [comp[i] for i in range(n) if i % 2 == 1]
N = len(odd)
N0 = 2 ** (N - 1).bit_length()
data = [None] * (2 * N0)
INF = (-1, 0)

def update(l, r, v):
	L = l + N0
	R = r + N0
	while L < R:
		if R & 1:
			R -= 1
			data[R - 1] = v
		if L & 1:
			data[L - 1] = v
			L += 1
		L >>= 1
		R >>= 1

def _query(k):
	k += N0 - 1
	s = INF
	while k >= 0:
		if data[k]:
			s = max(s, data[k])
		k = (k - 1) // 2
	return s

def query(k):
	return _query(k)[1]
ID = [-1] * n
for i in range(N):
	start = 0
	end = N
	while end - start > 1:
		test = (end + start) // 2
		if query(test) >= odd[i]:
			start = test
		else:
			end = test
	if start != 0:
		ID[2 * i + 1] = start
		update(start + 1, i + 1, (i, odd[i]))
	elif query(0) >= odd[i]:
		ID[2 * i + 1] = start
		update(start + 1, i + 1, (i, odd[i]))
	else:
		ID[2 * i + 1] = -1
		update(0, i + 1, (i, odd[i]))
dp = [0] * n
dp[0] = comp[0]
pre = [0] * n
for i in range(2, n, 2):
	id = ID[i - 1]
	if id == -1:
		res = comp[i - 1] * dp[i - 2]
		pre[i - 1] = res
	else:
		j = 2 * id + 1
		res = (comp[i - 1] * dp[i - 2] + pre[j] - comp[i - 1] * dp[j - 1]) % mod
		pre[i - 1] = res
	dp[i] = (comp[i] * res + dp[i - 2] + comp[i]) % mod
print(dp[-1] * Start * End % mod)