Strange Operation
Contest: Codeforces Round 659 (Div. 1)
Difficulty rating: 2800
Tags: combinatorics, data structures, dp

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 format:
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 format:
On a single line print the answer to the problem modulo $$$10^9+7$$$ ($$$1000000007$$$).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
000

Example output:
3

Example input:
0101

Example output:
6

Editorial:
Firstly the described operation can be seen as divide $$$s$$$ in sub-strings and take the bitwise or in each one. For each possible resultant string $$$w$$$ let's think in the following way of obtain it from $$$s$$$:
Suppose we already have a $$$1$$$ in $$$w$$$ in previous steps (if not it can be handled later) and we used the firsts $$$i$$$ characters of $$$s$$$ to get the firsts $$$j$$$ characters of $$$w$$$.
• if the $$$(j+1)$$$-th character in $$$w$$$ is $$$1$$$, find the next $$$1$$$ in $$$s$$$, (ie first $$$i' > i$$$ such that $$$s_{i'} = 1$$$), merge everything between the last $$$1$$$ and $$$i'-1$$$ and take the new $$$1$$$.
• if the $$$(j+1)$$$-th character in $$$w$$$ is $$$0$$$, and we have $$$k$$$ zeros after the last $$$1$$$ in $$$w$$$ find the next block of $$$k+1$$$ zeros in $$$s$$$, (ie first $$$i' > i$$$ such that for each $$$(0 \le k' \le k)$$$ $$$s_{i' - k'} = 0$$$), if $$$i'$$$ is equal to $$$i+1$$$ just append the new $$$0$$$ to $$$w$$$ otherwise merge everything between the last $$$1$$$ and $$$i'-k$$$ and take the new zeros from $$$i'-k+1$$$ to $$$i'$$$.We can prove that in this way every possible resultant string $$$w$$$ is generated in a unique way and it uses the minimum number of characters from $$$s$$$ to obtain $$$w$$$.
So we can start thinking about dynamic programming keeping in mind this greedy.
Let $$$dp(i)$$$ be the number of strings that we can obtain using the last $$$n-i$$$ characters from $$$s$$$, the transitions are the previous described two cases, taking care of the case of ending with certain numbers of $$$0$$$.
Therefore:
• If there is at least a $$$1$$$ in $$$s$$$, let $$$i$$$ be the first position such that $$$s_i = 1$$$, answer equals $$$dp(i) \cdot i$$$ (because we start assuming that there exists some previous $$$1$$$ and before this $$$1$$$ there are exactly $$$i$$$ possibilities: empty, one $$$0$$$, two $$$0$$$s, ..., $$$i - 1$$$ $$$0$$$s).
• Otherwise answer is $$$|s|$$$ (because $$$s$$$ consists of all $$$0$$$).
Time complexity: $$$O(n)$$$