codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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