P2246 SAC#1 - Hello World (Enhanced Version)

One day, the silly pipapi was studying programming with a rather poor handout.

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$.

The input contains several lines, which together form an article. The article ends at `EOF` (end of file).

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

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