A12185. The Fair Nut and String
编程题
普及/提高-
知识点
题目描述
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$ .
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]$ .
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]$ .