Minimum number of steps
time limit per test 2 second memory limit per test 256 megabytes
We have a string of letters ‘a’ and ‘b’. We want to perform some operations on it. On each step we choose one of substrings “ab” in the string and replace it with the string “bba”. If we have no “ab” as a substring, our job is done. Print the minimum number of steps we should perform to make our job done modulo 1e9+7.
The string “ab” appears as a substring if there is a letter ‘b’ right after the letter ‘a’ somewhere in the string.

传送门:CF805D

Input

The first line contains the initial string consisting of letters 'a' and 'b' only with length from 1 to 1e6.

Output

Print the minimum number of steps modulo 1e9+7.

Sample Input

1
2
3
ab

aab

Sample Output

1
2
3
1

3

题解

问一个字符串中的ab换成bba,到不需要换最少需要多少步 模拟一下,首先不要换的条件是所有a都到b的后面 而变换一下相当于所经过的b的个数乘以二 那么找到最后一个b,然后往前扫,用count记录b的个数,扫到b:count++ 扫到a 结果加上count 然后count*2 注意每步都要取模 否则会溢出
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.*;  
import java.util.*;
public class Main {
static int mod=(int) (1e9+7);
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
while (sc.hasNext()) {
String s=sc.next();
long count=0;
int index=-1;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='b'){
index=i;
}
}
long t=0;
for(int i=index;i>=0;i--){
if(s.charAt(i)=='b'){
t=(t+1)%mod;
}
else{
count=(count+t)%mod;
t=(t*2)%mod;
}
}
pw.println(count);
pw.flush();
}
}
}