codeforces#P1084C. The Fair Nut and String
The Fair Nut and String
Description
The Fair Nut found a string . The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences , such that:
- For each (), 'a'.
- For each (), there is such that and 'b'.
The Nut is upset because he doesn't know how to find the number. Help him.
This number should be calculated modulo .
The first line contains the string () consisting of lowercase Latin letters.
In a single line print the answer to the problem — the number of such sequences modulo .
Input
The first line contains the string () consisting of lowercase Latin letters.
Output
In a single line print the answer to the problem — the number of such sequences modulo .
Samples
Note
In the first example, there are possible sequences. , , , , .
In the second example, there are possible sequences. , , , .
In the third example, there are possible sequences. , , .