C. 2023.04.04-算法岗-第三题-子序列的权值和

2023.04.04-算法岗-第三题-子序列的权值和

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

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

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

例如:reddredd 权值为1,redredrredredr 权值为2,reedreed 权值为0

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

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

输入描述

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

输出描述

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

样例

输入

rredd

输出

真题模拟赛第四场|Ant|2023.04.04算法岗笔试

Not Attended
Status
Done
Rule
IOI
Problem
3
Start at
2023-4-14 19:00
End at
2023-4-14 20:20
Duration
1.3 hour(s)
Host
Partic.
81