Background

T1 The answer needs to be modulo 1000000007 (10^9+7), please resubmit, we apologize for the inconvenience!

One day, the foolish pipapi was studying programming design from a certain poor quality handout.

Problem Description

On one page of the handout, he saw an article. This article consists of English letters (both uppercase and lowercase), digits, and whitespace characters (tabs/spaces/line breaks).

pipapi recalled the Hello World program he had recently learned to write. He was very curious about how many times the subsequence "HelloWorld" appeared in this article.

Since pipapi is foolish, case sensitivity means nothing to him; therefore, subsequences like "hEllOWorLD" are also acceptable. Spaces between O and W are also optional; that is, "HelloWorld" is acceptable. According to the standard solution, spaces are not considered.

Two subsequences are considered the same if and only if each character's position is identical.

Since the answer may be very large, output the result modulo 1000000007 (10^9+7).

Input Format

The input contains several lines. The content of these lines together constitutes an article.

The article ends with EOF (end of file).

Output Format

The output contains only one integer, representing the number of times "Hello World" appears in the article.

Sample Input and Output

Sample Input #1

HhEeLlLlOoWwOoRrLlDd

Sample Output #1

1536

Sample Input #2

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 

Sample Output #2

273

Notes

Let n be the length of the input article (number of characters).

For 20% of the data, n <= 20.

For 50% of the data, n <= 500.

For all the data, 15 <= n <= 500000.

见题面 Input 部分

见题面 Output 部分