The Fair Nut and String
题意翻译
给出一个只包含小写字母的串 $s$,询问满足以下条件的子序列的个数:
1、这个子序列中的所有字符都是小写字母$a$。
2、如果这个子序列的长度大于$1$,那么这个子序列中的每两个字母之间一定要包含一个小写字母$b$。
答案模$10^9 + 7$。
$|s| \leq 10^5$。
题目描述
The Fair Nut found a string $ s $ . The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences $ p_1, p_2, \ldots, p_k $ , such that:
1. For each $ i $ ( $ 1 \leq i \leq k $ ), $ s_{p_i} = $ 'a'.
2. For each $ i $ ( $ 1 \leq i < k $ ), there is such $ j $ that $ p_i < j < p_{i + 1} $ and $ s_j = $ 'b'.
The Nut is upset because he doesn't know how to find the number. Help him.
This number should be calculated modulo $ 10^9 + 7 $ .
输入输出格式
输入格式
The first line contains the string $ s $ ( $ 1 \leq |s| \leq 10^5 $ ) consisting of lowercase Latin letters.
输出格式
In a single line print the answer to the problem — the number of such sequences $ p_1, p_2, \ldots, p_k $ modulo $ 10^9 + 7 $ .
输入输出样例
输入样例 #1
abbaa
输出样例 #1
5
输入样例 #2
baaaa
输出样例 #2
4
输入样例 #3
agaa
输出样例 #3
3
说明
In the first example, there are $ 5 $ possible sequences. $ [1] $ , $ [4] $ , $ [5] $ , $ [1, 4] $ , $ [1, 5] $ .
In the second example, there are $ 4 $ possible sequences. $ [2] $ , $ [3] $ , $ [4] $ , $ [5] $ .
In the third example, there are $ 3 $ possible sequences. $ [1] $ , $ [3] $ , $ [4] $ .