1084C.md (1342B)
1 Source: https://codeforces.com/problemset/problem/1084/C 2 3 C. The Fair Nut and String 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 1. For each $i$ ($1 \leq i \leq k$), $s_{p_i} =$ 'a'. 24 2. For each $i$ ($1 \leq i \lt k$), there is such $j$ that $p_i \lt j \lt p_{i + 1}$ and $s_j =$ 'b'. 25 26 The Nut is upset because he doesn't know how to find the number. Help him. 27 28 This number should be calculated modulo $10^9 + 7$. 29 30 Input 31 32 The first line contains the string $s$ ($1 \leq |s| \leq 10^5$) consisting of lowercase Latin letters. 33 34 Output 35 36 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$. 37 38 Examples 39 40 Input 41 42 ``` 43 abbaa 44 ``` 45 46 Output 47 48 ``` 49 5 50 ``` 51 52 Input 53 54 ``` 55 baaaa 56 ``` 57 58 Output 59 60 ``` 61 4 62 ``` 63 64 Input 65 66 ``` 67 agaa 68 ``` 69 70 Output 71 72 ``` 73 3 74 ``` 75 76 Note 77 78 In the first example, there are $5$ possible sequences. $[1]$, $[4]$, $[5]$, $[1, 4]$, $[1, 5]$. 79 80 In the second example, there are $4$ possible sequences. $[2]$, $[3]$, $[4]$, $[5]$. 81 82 In the third example, there are $3$ possible sequences. $[1]$, $[3]$, $[4]$.