|
||||||||||
Yiwen with SqcTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 1138 Accepted Submission(s): 499 Problem Description Recently, Yiwen is learning Assembly Language. Since Yiwen is a genius in computer science, he proposed an extremely valuable technique called Basic Instruction Technology. Using this kind of technique, Yiwen can create numerous different instruction. Some of these instruction can be used to calculate some special eigenvalue of a string, such as $sqc$. For a string $s$, let $s_i$ be the $i^{th}$ character of it. Instruction sqc has 4 operands $s$, $l$, $r$ and $c$, where $s$ is a string, $1 \leq l \leq r \leq n$, $c$ is a character represented by ASCII value. $sqc(s,l,r,c)$ returns the number of character $c$ in substring $s_l \cdots s_r$. Yiwen wants you to calculate following expression for the given string $s$: $$\sum_{c=97}^{122}\sum_{i=1}^{n}\sum_{j=i}^{n} sqc(s,i,j,c)^2$$ Note that the ASCII value of 'a' is $97$ and the ASCII value of 'z' is $122$. The answer will probably be very huge, so just calculate the answer modulo $998244353$. Input The input consists of multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 100$) -- the number of test cases. For each test case, the only line contains a string $s$ ($|s| \leq 10^5$) consists of lowercase English letters. It is guaranteed that the sum of $|s|$ over all test cases does not excceed $5 \times 10^6$. Output For each test case, output your answer modulo $998244353$ in a single line. Sample Input
Sample Output
Source | ||||||||||
|