C. The Fair Nut and String
combinatorics; dp; implementation
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: For each \(i\) (\(1 \leq i \leq k\)), \(s_{p_i} =\) 'a'. 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\).
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]\).