Problem I: 字符串计数

"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $26$ 正确数量 $11$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 字符串 动态规划

abadedde 是个特殊的字符序列,给定一个长度为 N 的字符串 s,请你找出 s 中含有多少个 abadedde 子字符序列。 


字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如 abe 是 abcde 的一个子序列,而 aec 不是)

输出的第一行为一个正整数 T 表示共有 T 个测试用例; 

对于每个测试用例,在单独的一行中给出字符串 si(0 <= i < T), si 中仅包含小写字母。

对于每个 在单独的一行中输出其有多少个 abadedde 字符序列。 


由于这个数可能很大,所以要求输出的答案对 1000000007 取余。

4
abadedde
abadeddee
abadeddeddeddadaadadadaadaadadaaaadaa
abadeddedadaadadadadadadaadaadadadaddae
1
2
10
394

1 <= T <= 1000

1 <= Ni <= 105

1 <= ∑1Ni  ≤ 106