305745: CF1084C. The Fair Nut and String

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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] $ .

Input

题意翻译

给出一个只包含小写字母的串 $s$,询问满足以下条件的子序列的个数: 1、这个子序列中的所有字符都是小写字母$a$。 2、如果这个子序列的长度大于$1$,那么这个子序列中的每两个字母之间一定要包含一个小写字母$b$。 答案模$10^9 + 7$。 $|s| \leq 10^5$。

加入题单

上一题 下一题 算法标签: