题目描述

给定一个仅由字符 'a' 和 'b' 构成的字符串 $s$。

你可以对这个字符串进行任意次如下操作：

从字符串中找到任意一个子串 "ab"，并将其替换成 "bba"。

你希望使用最少的操作次数使字符串中不存在子串 "ab"。

求：使字符串中不存在子串 "ab" 所需的最少操作次数。由于操作次数可能很大，所以你只需要输出最少操作次数模 $10^9+7$ 的结果即可。

注：

• 一个字符串的子串是从字符串中顺序取出若干个连续的字符组成的字符串；
• 整数 $a$ 模 $b$ 的结果即为 $a \div b$ 的余数。

输入格式

一行，一个字符串 $s$。$s$ 仅由字符 'a' 和 'b' 构成，且长度不超过 $10^6$。

输出格式

输出一个整数，表示使字符串中不存在子串 "ab" 所需的最少操作次数模 $10^9+7$ 的结果。

input

ab

output

1

input

aab

output

3

说明/提示

样例解释

• 样例1："ab" $\rightarrow$ "bba"
• 样例2："aab" $\rightarrow$ "abba" $\rightarrow$ "bbaba" $\rightarrow$ "bbbbaa"

数据规模与约定

设 $|s|$ 表示字符串 $s$ 的长度，则：

• 对于 $20\%$ 的数据，$|s| \le 10$
• 对于 $50\%$ 的数据，$|s| \le 10^3$
• 对于 $80\%$ 的数据，$|s| \le 10^5$
• 对于 $100\%$ 的数据，$1 \le |s| \le 10^6$，且 $s$ 仅由字符 'a' 和 'b' 构成