Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. The Fair Nut and String

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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$$$.

Input

The first line contains the string $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$) consisting of lowercase Latin letters.

Output

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

Examples

Input

abbaa

Output

5

Input

baaaa

Output

4

Input

agaa

Output

3

Note

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2021 22:08:32 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|