#P1084C. The Fair Nut and String

    ID: 4515 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>combinatoricsdpimplementation*1500

The Fair Nut and String

No submission language available for this problem.

Description

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:

  1. For each $i$ ($1 \leq i \leq k$), $s_{p_i} =$ 'a'.
  2. 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$.

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

Samples

abbaa

5
baaaa

4
agaa

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