Strange Operation

题意翻译

给定一个 01 串 $a$，$|a| = n$。在一次操作中，你可以选择任意一个 $i\in[1,|a|)$，令 $a_i=\max(a_i,a_{i+1})$，然后将 $a_{i+1}$ 删除，01 串长度减一。你可以进行不超过 $n-1$ 次操作，问一共能获得多少种 01 串，答案对 $10^9+7$ 取模。 $n\in\left[1,10^6\right]$。

题目描述

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 $ )?

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

000

输出样例 #1

3

输入样例 #2

0101

输出样例 #2

6

输入样例 #3

0001111

输出样例 #3

16

输入样例 #4

00101100011100

输出样例 #4

477

说明

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.