← 返回题目列表

Codeforces · 804/B

B. 最小步数

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

我们有一串字母“a”和“b”。我们想要对其执行一些操作。在每一步中,我们选择字符串中的子字符串“ab”之一,并将其​​替换为字符串“bba”。如果我们没有“ab”作为子字符串,我们的工作就完成了。打印完成工作所需执行的最少步骤数(模 109 + 7)。

如果字符串中某处字母“a”后面有字母“b”,则字符串“ab”将显示为子字符串。

输入

第一行包含仅由字母“a”和“b”组成的初始字符串,长度为 1 到 106。

输出

打印以 109 + 7 为模的最小步数。

示例

输入 #1

ab

输出 #1

1

输入 #2

aab

输出 #2

3

注意

第一个示例:“ab”→“bba”。

第二个示例:“aab”→“abba”→“bbaba”→“bbbbaa”。