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 (tab/space/newline).

pipapi recalled the Hello World program he had just learned to write. He was very curious: in this article, how many times does Hello World occur as a subsequence? (ignoring case and spaces)

Two subsequences are the same if and only if the positions of every character are identical.

Since the answer may be large, please output the answer modulo ${10}^9+7$.

Input Format

The input contains several lines, which together form an article.

The article ends at EOF (end of file).

Output Format

Output only a single integer, representing how many times Hello World appears in the article.

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

Hint

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

For $20\%$ of the testdata, $n \le 20$.

For $50\%$ of the testdata, $n \le 500$.

For all the testdata, $15 \le n \le 500000$.

Translated by ChatGPT 5