codeforces#P1084C. The Fair Nut and String

The Fair Nut and String

Description

The Fair Nut found a string ss. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,,pkp_1, p_2, \ldots, p_k, such that:

  1. For each ii (1ik1 \leq i \leq k), spi=s_{p_i} = 'a'.
  2. For each ii (1i<k1 \leq i < k), there is such jj that pi<j<pi+1p_i < j < p_{i + 1} and sj=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 109+710^9 + 7.

The first line contains the string ss (1s1051 \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 p1,p2,,pkp_1, p_2, \ldots, p_k modulo 109+710^9 + 7.

Input

The first line contains the string ss (1s1051 \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 p1,p2,,pkp_1, p_2, \ldots, p_k modulo 109+710^9 + 7.

Samples

输入数据 1

abbaa

输出数据 1

5

输入数据 2

baaaa

输出数据 2

4

输入数据 3

agaa

输出数据 3

3

Note

In the first example, there are 55 possible sequences. [1][1], [4][4], [5][5], [1,4][1, 4], [1,5][1, 5].

In the second example, there are 44 possible sequences. [2][2], [3][3], [4][4], [5][5].

In the third example, there are 33 possible sequences. [1][1], [3][3], [4][4].