题目背景

T1答案要mod1000000007(10^9+7)，请重新提交，非常抱歉！

一天，智障的pipapi正在看某辣鸡讲义学程序设计。

题目描述

在讲义的某一面，他看见了一篇文章。这篇文章由英文字母（大小写均有）、数字、和空白字符（制表/空格/回车）构成。

pipapi想起了他最近刚刚学会写的Hello World程序。他非常好奇，这篇文章中，“HelloWorld”作为子序列到底出现过多少次呢？

由于papapi是个智障，大小写对于他而言毫无区别；因此，“hEllOWorLD”这样的子序列也是可以接受的。O和W之间的空格是也是可以少的；也就是说，“HelloWorld”是可以的。根据标程的意思，就是没有空格，不用考虑空格的情况。

两个子序列相同当且仅当它们每一个字符所在的位置都相同。

由于答案可能很大，请输出结果对1000000007(10^9+7)的余数。

输入输出格式

输入格式：

输入包含若干行。这些行的内容共同构成一篇文章。

文章以EOF（文件结尾）结束。

输出格式：

输出仅包含一个整数，表示这篇文章中“Hello World”出现的次数。 d

输入输出样例

HhEeLlLlOoWwOoRrLlDd

1536

Gou Li Guo Jia Sheng Si Yi

Qi Yin Huo Fu Bi Qu Zhi

River can feed people

Also can race boats

Hall Ellen Ok Words locked 

273

说明

记n为输入的文章的长度（字符数）。

对于20%的数据，n <= 20。

对于50%的数据，n <= 500。

对于所有的数据，15 <= n <= 500000。

普通DP。

f[i][j]记录总串匹配到第i位，序列末尾是helloworld第j位的方案数。

线性DP扫描即可。

第一维可以优化。

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int mod=1e9+;

 const int mxn=;

 char c[]="$helloworld";

 int f[];

 char s[];

 int main(){

     f[]=;

     int len;

     while(scanf("%s",s+)!=EOF){

         len=strlen(s+);

         for(int i=;i<=len;i++){

             char ch=tolower(s[i]);

             for(int j=;j;j--){

                 if(c[j]==ch){

                     (f[j]+=f[j-])%=mod;

                 }

             }

         }

     }

     printf("%d\n",f[]%mod);

     return ;

 }