CF1084C.The Fair Nut and String

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The Fair Nut found a string ss . The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,,pkp_1, p_2, \ldots, p_k , such that:

  1. For each ii ( 1ik1 \leq i \leq k ), spi=s_{p_i} = 'a'.
  2. For each ii ( 1i<k1 \leq i < k ), there is such jj that pi<j<pi+1p_i < j < p_{i + 1} and sj=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 109+710^9 + 7 .

输入格式

The first line contains the string ss ( 1s1051 \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 p1,p2,,pkp_1, p_2, \ldots, p_k modulo 109+710^9 + 7 .

输入输出样例

  • 输入#1

    abbaa
    

    输出#1

    5
  • 输入#2

    baaaa
    

    输出#2

    4
  • 输入#3

    agaa
    

    输出#3

    3

说明/提示

In the first example, there are 55 possible sequences. [1][1] , [4][4] , [5][5] , [1,4][1, 4] , [1,5][1, 5] .

In the second example, there are 44 possible sequences. [2][2] , [3][3] , [4][4] , [5][5] .

In the third example, there are 33 possible sequences. [1][1] , [3][3] , [4][4] .

首页