题目描述

嘤嘤定义一个字符串的权值为：该字符串包含的 $abba$ 子序列的数量。

给定一个字符串，试求它的所有连续子串的权值和。答案请对 $10^9 + 7$ 取模。

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

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

输入文件 substring.in

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

输出文件 substring.out

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

abbaa

3

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

提示

样例 2 见附加文件。

对于 $10\%$ 的数据，保证字符串长度不超过 $20$。

对于 $20\%$ 的数据，保证字符串长度不超过 $200$。

对于 $30\%$ 的数据，保证字符串长度不超过 $2000$。

对于 $50\%$ 的数据，保证字符串长度不超过 $10^5$。

对于 $80\%$ 的数据，保证字符串长度不超过 $10^6$。

对于 $100\%$ 的数据，保证字符串长度不超过 $5×10^6$。