题目描述

嘤嘤定义一个字符串的权值为：该字符串包含的 "abba" 子序列的数量。给定一个字符串，请计算它的所有连续子串的权值和，并将答案对 $10^9 + 7$ 取模。

子串定义：字符串删除一个前缀和一个后缀（也可以不删）得到的字符串。例如，"arcaea"的子串有"arc"、"ca"等。

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

输入格式

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

输出格式

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

样例输入1

abbaa

样例输出1

3

"abba"的权值为 1，"abbaa"的权值为 2。权值之和为 1 + 2 = 3

备注

• 对于 10% 的数据，保证字符串长度不超过 $20$.
• 对于 20% 的数据，保证字符串长度不超过 $200$.
• 对于 30% 的数据，保证字符串长度不超过 $2000$.
• 对于 50% 的数据，保证字符串长度不超过 $10^5$.
• 对于 80% 的数据，保证字符串长度不超过 $10^6$.
• 对于 100% 的数据，保证字符串长度不超过 $5 \times 10^6$.