Nun Heh Heh Aaaaaaaaaaa

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1873    Accepted Submission(s): 1031

 

Problem Description Vasily Tadokorov is a stringologist. He thinks a string is fragrant if it can be divided into two parts — 횗횞횗횑횎횑횑횎횑 as the prefix and a number of (excluding 0) 횊 as the suffix. For example, 횗횞횗횑횎횑횑횎횑횊횊횊횊횊횊 is fragrant, but 횗횞횗횑횎횑횑횎횑 and 횗횞횗횑횎횑횑횎횑횘횘횘횊횊횊 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.  

Input The first line contains an integer T (1≤T≤1000), denoting the number of strings.

Each of the next T lines contains a string S (1≤|S|≤105) consisting of lowercase English letters.

The total length of the strings in the input will not exceed 106.  

Output For each of the given T strings, output the answer modulo 998244353.  

Sample Input

2 nunhehhehahaahahahahahahaahaahahahahha nunhehhehhehhahaahahahaahaahahaaaahaa  

Sample Output

114514 1919810

const int mod=998244353;
int t;
ll dp[11][10100];
//dp[i][j]是s的前j位中ss中1-i字符串出现的次数
int main(){
    cin>>t;
    while (t--) {
        ll ans=0;
        string ss="nunhehheh";
        string s;
        cin>>s;
        s="0"+s;
        int len=s.size();
        int a[100010];
        mms(a,0);
        for(int i=len;i>=1;i--)
            a[i]=a[i+1]+(s[i]=='a');
        for(int i=1;i<=len;i++){
            dp[1][i]=(dp[1][i-1]+(s[i]=='n'))%mod;
                        dp[2][i]=(dp[2][i-1]+dp[1][i-1]*(s[i]=='u'))%mod;
                        dp[3][i]=(dp[3][i-1]+dp[2][i-1]*(s[i]=='n'))%mod;
                        dp[4][i]=(dp[4][i-1]+dp[3][i-1]*(s[i]=='h'))%mod;
                        dp[5][i]=(dp[5][i-1]+dp[4][i-1]*(s[i]=='e'))%mod;
                        dp[6][i]=(dp[6][i-1]+dp[5][i-1]*(s[i]=='h'))%mod;
                        dp[7][i]=(dp[7][i-1]+dp[6][i-1]*(s[i]=='h'))%mod;
                        dp[8][i]=(dp[8][i-1]+dp[7][i-1]*(s[i]=='e'))%mod;
                        dp[9][i]=(dp[8][i-1]*(s[i]=='h'))%mod;
                        if(dp[9][i])
                            ans=ans%mod+(dp[9][i]*(pows(2,(a[i+1]),mod)-1))%mod;
                        ans%=mod;
        }
        cout<