Description

嘤嘤定义一个字符串的权值为：该字符串包含的"abba"子序列的数量。 给定一个字符串，试求它的所有连续子串的权值和。答案请对 109 + 7取模。

子串定义： 字符串删除一个前缀和一个后缀(也可以不删) 得到的字符串。例如， "aTcaea"的子串有"aTc" 、"ca"等。

子序列定义： 字符串删除若干个字符(也可以不删) 得到的字符串。例如， "aTcaea"的子序 列有"aca"等。

Input Format

输入一个仅包含小写字母的字符串。

Output Format

所有连续子串的权值和。答案对 10^9 + 7 取模。

abbaa

3

Hint

样例一说明 "abba"的权值为 1， "abbaa"的权值为 2。权值之和为 1 + 2 = 3。

数据范围 对于10%的数据，保证字符串长度不超过 20 。 对于20%的数据，保证字符串长度不超过 200 。 对于30%的数据，保证字符串长度不超过 2000 。 对于50%的数据，保证字符串长度不超过 10^5 。 对于80%的数据，保证字符串长度不超过 10^6 。 对于100%的数据，保证字符串长度不超过 5 × 10^6 。