对模式串 abc，我们考虑每个字符 b 的位置对答案的贡献。对于每个 b，它左侧可以删除字符得到 a，右侧可以删除字符得到 c，两侧的方案数相乘即为该 b 能产生的 abc 总数。累加即得答案。

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

题目内容

给定一个由小写字母组成的字符串 $S$，我们固定一个模式串 abc（即字符 'a','b','c' 依次相连）。

对于一个字符串 $T$，定义其「模式出现次数」为 $T$ 中等于 abc 的连续子串出现的次数。例如，$T$ 为 abcc 时次数为 $1$，abcabc 时为 $2$，acb 时为 $0$。

现在考虑从 $S$ 中删除零个或多个字符（但不能删除全部字符），保持剩余字符的相对顺序，所能得到的所有新字符串。对每一个这样的新字符串，求其模式出现次数。请计算所有这些次数的总和，并将结果对 $10^9+7$ 取余后输出。

字符串 $S$ 的长度 $n$ 满足 $1 \le n \le 10^5$。

输入描述

输入仅一行，包含一个长度在 $1$ 到 $10^5$ 之间的字符串 $S$，仅由小写英文字母组成。

输出描述

输出一个整数，表示上述总和对 $10^9+7$ 取模的结果。

样例1

输入

red

输出

1

说明

字符串 $S = \text{red}$，长度 $n=3$。

所有删除字符得到的新字符串中，只有保留全部字符的 \text{red} 包含一次模式串 \text{red}。唯一的三元组 $(i,j,k)=(1,2,3)$ 满足 $s_1=\text{'r'}, s_2=\text{'e'}, s_3=\text{'d'}$，贡献为 $2^{1-1} \times 2^{3-3} = 1$。因此总次数为 1。

样例2

输入

reed

输出

2

说明

字符串 $S = \text{reed}$，长度 $n=4$。

满足条件的三元组有两个：

• $(i,j,k)=(1,2,4)$：$s_1=\text{'r'}, s_2=\text{'e'}, s_4=\text{'d'}$，贡献 $2^{0} \times 2^{0} = 1$；
• $(i,j,k)=(1,3,4)$：$s_1=\text{'r'}, s_3=\text{'e'}, s_4=\text{'d'}$，贡献 $2^{0} \times 2^{0} = 1$。

相当于在 $S$ 中删除第 2 个字符得到 \text{red}，或删除第 3 个字符得到 \text{red}，每种情况在新字符串中出现 1 次模式串，总和为 2。

样例3

输入

redred

输出

18

说明

字符串 $S = \text{redred}$，长度 $n=6$。

满足条件的三元组及贡献如下：

• $(1,2,3)$：$2^{1-1} \times 2^{6-3} = 2^{0} \times 2^{3} = 8$；
• $(1,2,6)$：$2^{0} \times 2^{0} = 1$；
• $(1,5,6)$：$2^{0} \times 2^{0} = 1$；
• $(4,5,6)$：$2^{3} \times 2^{0} = 8$。

总和为 $8 + 1 + 1 + 8 = 18$，对 $10^9+7$ 取模后结果仍为 18。

样例4

输入

a

输出

0

说明

字符串 $S = \text{a}$，长度 $n=1$，不包含模式串 \text{red} 所需的任何字符，不存在满足条件的三元组，因此总次数为 0。这也是一个简单的边界情况。