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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\ndef mint():\n\treturn int(minp())\n\ndef mints():\n\treturn list(map(int, minp().split()))\n\ndef solve():\n\tMOD = int(1e9+7)\n\twas = set()\n\ts = list(map(int, minp()))\n\tn = len(s)\n\n\tfirst, last = None, None\n\n\tfor i in range(n):\n\t\tv = s[i]\n\t\tif v == 1:\n\t\t\tfirst = i\n\t\t\tbreak\n\tif first is None:\n\t\tprint(n)\n\t\treturn\n\n\tdp = [0]*n\n\tdp[first] = 1\n\tst = []\n\tstv = []\n\tr = 0\n\ti = first\n\twhile i < n:\n\t\tj = i + 1\n\t\twhile j < n and s[j] == 0:\n\t\t\tj += 1\n\t\tr = (r + dp[i]) % MOD\n\t\tif j == n:\n\t\t\tlast = i\n\t\t\tbreak\n\t\tc = j - i - 1\n\t\tadd = 0\n\t\tst.append(0)\n\t\tstv.append(dp[i])\n\t\twhile len(st) > 0 and st[-1] <= c:\n\t\t\tv = st.pop()\n\t\t\td = stv.pop()\n\t\t\tdp[j] = (dp[j] + d*(c - v + 1)) % MOD\n\t\t\tadd += d\n\t\tif len(st) > 0 and st[-1] == c + 1:\n\t\t\tstv[-1] = (stv[-1] + add) % MOD\n\t\telse:\n\t\t\tst.append(c + 1)\n\t\t\tstv.append(add)\n\t\ti = j\n\tprint((r * (first+1) * (n-last)) % MOD)\n\nsolve()\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15393