我们有一串字母“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”。