← 返回题目列表

Codeforces · 1383/E

E. 奇怪的操作

中文机器翻译题面 查看原题

Koa 考拉有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。 Koa 最多可以执行 $$$n-1$$$(可能为零)以下形式的操作:

在一次操作中,Koa 为 $$$1 \le i < |s|$$$ 的某些 $$$i$$$ 选择位置 $$$i$$$ 和 $$$i+1$$$,并将 $$$s_i$$$ 设置为 $$$max(s_i, s_{i+1})$$$。然后Koa从$$$s$$$中删除位置$$$i+1$$$(删除后,将剩余部分连接起来)。

请注意,每次操作后 $$$s$$$ 的长度都会减少 $$$1$$$。

Koa 通过执行不超过 $$$n-1$$$(可能为零)的模 $$$10^9+7$$$ ($$$1000000007$$$) 运算可以获得多少个不同的二进制字符串?

输入

输入的唯一行包含二进制字符串 $$$s$$$ ($$$1 \le |s| \le 10^6$$$)。对于所有 $$$i$$$ ($$$1 \le i \le |s|$$$) $$$s_i = 0$$$ 或 $$$s_i = 1$$$。

输出

在一行上打印问题的答案,模 $$$10^9+7$$$ ($$$1000000007$$$)。

示例

输入 #1

000

输出 #1

3

输入 #2

0101

输出 #2

6

输入 #3

0001111

输出 #3

16

输入#4

00101100011100

输出#4

477

注意

在第一个样本中,Koa 可以获取二进制字符串:$$$0$$$、$$$00$$$ 和 $$$000$$$。

在第二个样本中,Koa 可以获得二进制字符串:$$$1$$$、$$$01$$$、$$$11$$$、$$$011$$$、$$$101$$$ 和 $$$0101$$$。例如:

- 从$$$0101$$$获取$$$01$$$ Koa可以如下操作:$$$0101 \rightarrow 0(10)1 \rightarrow 011 \rightarrow 0(11) \rightarrow 01$$$。
- 从$$$0101$$$获取$$$11$$$ Koa可以如下操作:$$$0101 \rightarrow (01)01 \rightarrow 101 \rightarrow 1(01) \rightarrow 11$$$。

括号表示每次操作中 Koa 选择的两个位置。