题目描述

小杰定义一个字符串是"好串"，当且仅当该字符串包含"ab"子序列。

现在小杰拿到了一个仅由'a'和"b'组成的字符串。他想知道，该字符串有多少子序列是好串?

定义字符串的子序列为: 字符串从左到右取若干字符(在原串中可以不连续)组成的新串。例如，"arcaea"的子序列有"ace"等。

输入描述

一个仅包含'a'和'b'的长度为n字符串.

1 <= n <= 105。

输出描述

好子序列的数量。由于答案可能过大，请对109+ 7取模。

输入示例

abab

输出示例

8

提示信息

长度为4的子序列"abab"是好串。长度为3的子序列共有4个，都是好串，长度为2的子序列仅"ab"是好串，共有3个"ab"子序列。答案是1+4+3=8。

时间限制：c/c++：1s；其他语言：3s。