Vasily Tadokorov is a stringologist. He thinks a string is fragrant if it can be divided into two parts ― $\texttt{nunhehheh}$ as the prefix and a number of (excluding 0) a as the suffix. For example, nunhehhehaaaaaa is fragrant, but nunhehheh and nunhehhehoooaaa are not fragrant.
Today Vasily Tadokorov has some strings consisting of lowercase English letters. For each string, he wants to know how many subsequences of this string are fragrant. A string a is a subsequence of a string b if a can be obtained from b by deletion of several (including 0) characters.
2 nunhehhehahaahahahahahahaahaahahahahha nunhehhehhehhahaahahahaahaahahaaaahaa
114514 1919810