题目内容

小红是一名热爱字符串算法的程序员。他最近遇到了一个有趣的问题。

给定一个字符串 $s$，字符串中包含多少个 red 子串，就给这个字符串一个权值，权值就是 red 子串的数量。

例如:$redd$ 权值为1，$redredr$ 权值为2,$reed$ 权值为0

现在考虑计算一个字符串 $s$ 所有非空子序列的权值和。 答案可能很大，请对$1e9+7$取模

长为 $n$ 的字符串的非空子序列为 $2^n-1$ 个。

输入描述

输入第一行为一个字符串$s (1 \leq |s| \leq 100000)$。

输出描述

输出字符串所有非空子字符串的权值和。

样例

输入

rredd

输出

9

思路：前后缀分解+贡献法计数+乘法原理

考虑枚举第i个元素对结果的贡献，即第i个元素可以构成多少个"red"子序列，如果第i个元素不是字符'e'，那么对结果的贡献肯定为0，如果是'e'，则需要去统计i左边有多少个字符'r'以及右边有多少个字符'd'，右边有多少个字符'd'可以使用一个后缀数组g预处理一下，对于左边的每一个字符'r'，设它对应的下标为j，$0\le j \le n-1$，它所能构成的非空子序列数量为$2^j$

（即它左边有多少个字符，比如j=0，它左边没有字符，就只有它自己一种选择，对应方案数为$2^0=1$）

这个地方，题目也给了提示：