Problem: 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 ≤ 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 ≤ |s| ≤ 10^6). For all i (1 ≤ i ≤ |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 → 0(10)1 → 011 → 0(11) → 01. 
  * to obtain 11 from 0101 Koa can operate as follows: 0101 → (01)01 → 101 → 1(01) → 11. 



Parentheses denote the two positions Koa selected in each operation.

Solution (in PYTHON3):

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