← 返回题目列表

Codeforces · 1084/C

C. 公平的坚果和绳子

中文机器翻译题面 查看原题

Fair Nut 找到了字符串 $$$s$$$。该字符串由小写拉丁字母组成。坚果是一个好奇的家伙,所以他想找到严格递增序列 $$$p_1, p_2, \ldots, p_k$$$ 的数量,这样:

1. 对于每个 $$$i$$$ ($$$1 \leq i \leq k$$$),$$$s_{p_i} =$$$ 'a'。
2. 对于每个 $$$i$$$ ($$$1 \leq i < k$$$),存在 $$$j$$$ 使得 $$$p_i < j < p_{i + 1}$$$ 且 $$$s_j =$$$ 'b'。

坚果很沮丧,因为他不知道如何找到号码。帮助他。

该数字应以 $$$10^9 + 7$$$ 为模进行计算。

输入

第一行包含由小写拉丁字母组成的字符串 $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$)。

输出

在一行中打印问题的答案 - 此类序列 $$$p_1, p_2, \ldots, p_k$$$ 模 $$$10^9 + 7$$$ 的数量。

示例

输入 #1

abbaa

输出 #1

5

输入 #2

baaaa

输出 #2

4

输入 #3

agaa

输出 #3

3

注意

在第一个示例中,有 $$$5$$$ 可能的序列。 $$$[1]$$$、$$$[4]$$$、$$$[5]$$$、$$$[1, 4]$$$、$$$[1, 5]$$$。

在第二个示例中,有 $$$4$$$ 可能的序列。 $$$[2]$$$、$$$[3]$$$、$$$[4]$$$、$$$[5]$$$。

在第三个示例中,有 $$$3$$$ 可能的序列。 $$$[1]$$$、$$$[3]$$$、$$$[4]$$$。