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: competition

Starter code:

Solutions:
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)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
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
# a_iの現在の値を取得
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
    #print(i,start,odd[i])
    if start!=0:
        ID[2*i+1]=start
        update(start+1,i+1,(i,odd[i]))
    else:
        if 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
        #prel[i-1]=1
    else:
        j=2*id+1
        #res=(comp[i-1]*dp[i-2]+(comp[j]-comp[i-1])*premono[j])%mod
        res=(comp[i-1]*dp[i-2]+pre[j]-comp[i-1]*dp[j-1])%mod
        pre[i-1]=res
        #prel[i-1]=prel[j]+1
    dp[i]=(comp[i]*res+dp[i-2]+comp[i])%mod
#print(pre)
#print(dp)
print((dp[-1]*Start*End)%mod)


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)


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],i//2) for i in range(n) if i%2==1]
#print(odd)
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])

#print(ID[1::2])
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
        #prel[i-1]=1
    else:
        j=2*id+1
        #res=(comp[i-1]*dp[i-2]+(comp[j]-comp[i-1])*premono[j])%mod
        res=(comp[i-1]*dp[i-2]+pre[j]-comp[i-1]*dp[j-1])%mod
        pre[i-1]=res
        #prel[i-1]=prel[j]+1
    dp[i]=(comp[i]*res+dp[i-2]+comp[i])%mod
#print(pre)
#print(dp)
print((dp[-1]*Start*End)%mod)


import sys

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

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

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

def solve():
	MOD = int(1e9+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()


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()