Problem1305--警探PIPI

1305: 警探PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 72  Solved: 28
[Submit] [Status] [Web Board] [Creator:]

Description

最近CSU发生了两起特大盗窃案,猖狂的窃贼甚至还在作案现场留下了自己的名字“xiefang”,以及一张写满小写字母的字条。
警探PIPI赶到现场后,仔细研究起字条来,它发现看似毫无规律的字条隐藏着大幂幂:字条上字符串任意为“xiefang”的子序列的个数正是嫌疑人的无耻程度。
如果知道了嫌疑人的无耻程度,破案将事半功倍!请你帮帮PIPI计算“xiefang”的无耻程度是多少?由于TA实在太过无耻,请对1e9+7取模。
例如字符串“abc”的所有非空子序列为"a","b","c","ab","ac","bc","abc".

Input

单组样例。
一个字符串,长度不超过1e6.

Output

窃贼xiefang的无耻程度,即"xiefang"在字符串中作为子序列出现的次数。

Sample Input

xxiefang

Sample Output

2

Source/Category

中等