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.