Problem D
Decision Making
After getting introduced to gambling by your friends, you decided to try your luck at the casino. There, you encountered a very interesting game!
The game is played with a single coin and a set of $n$ strings $s_1, s_2, \ldots , s_ n$ consisting of the characters H and T. The coin will be flipped multiple times until a winner among the $n$ strings is determined.
Suppose the sequence of coin flips results in the string $v$, where $v_ i = \texttt{H}$ if the $i$th coin flip results in heads and $v_ i = \texttt{T}$ if the $i$th coin flip results in tails.
Then, a winner is determined if there exists a string $s_ i$ which occurs as a substring of $v$. If no such string exists, the game continues. If there are multiple such strings, then the winner is the string with the smallest index.
For example, suppose $s_1 = \texttt{HTT}$, $s_2 = \texttt{TTT}$, $s_3 = \texttt{HT}$, and $s_4 = \texttt{TTT}$.

If $v = \texttt{TT}$, then no winner has been determined and the game continues.

If $v = \texttt{TTHT}$, then the winner is $s_3$.

If $v = \texttt{TTT}$, then the winner is $s_2$, since it has a smaller index than $s_4$.
Note that $s_1$ can never be a winner, since if $s_1$ occurs as a substring of $v$, then $s_3$ will have occurred earlier as a substring of $v$. In this example, the probability of $s_2$ winning is $\frac{1}{8}$ and the probability of $s_3$ winning is $\frac{7}{8}$.
You don’t believe in the concept of luck, so you decide to compute the exact probability of winning for every string $s_ i$. Fortunately, you know that the coin is fair, so the probability of getting heads or tails is $\frac{1}{2}$ each.
It is guaranteed that the probability of winning for each string $s_ i$ can be represented as a rational number $\frac{P_ i}{Q_ i}$, where $Q_ i$ is coprime to $998\, 244\, 353$. You should output the value of $P_ i \cdot Q_ i^{1} \bmod 998\, 244\, 353$ for each string.
Input
The first line of input contains one integer $n$, the number of strings ($1 \leq n \leq 100$).
The next $n$ lines of input contains the string $s_ i$ consisting of the characters H and T ($1 \leq s_ i \leq 100\, 000$). The sum of the lengths of all strings does not exceed $100\, 000$.
It is guaranteed that the probability of winning for each string $s_ i$ can be represented as a rational number $\frac{P_ i}{Q_ i}$, where $Q_ i$ is coprime to $998\, 244\, 353$.
Output
Output $n$ lines, where the $i$th line contains the value of $P_ i \cdot Q_ i^{1} \bmod 998\, 244\, 353$ — the probability of winning for the string $s_ i$.
Explanation of Sample
For the first sample, the probability of winning for each string is as follows:

$s_1$ wins with probability $0$.

$s_2$ wins with probability $\frac{1}{8}$.

$s_3$ wins with probability $\frac{7}{8}$.

$s_4$ wins with probability $0$.
For the second sample, the probability of winning for each string is as follows:

$s_1$ wins with probability $\frac{7}{302} \approx 0.023179$.

$s_2$ wins with probability $\frac{148}{302} \approx 0.490066$.

$s_3$ wins with probability $\frac{147}{302} \approx 0.486755$.
Sample Input 1  Sample Output 1 

4 HTT TTT HT TTT 
0 873463809 124780545 0 
Sample Input 2  Sample Output 2 

3 HTHTHTHT THHT HTTH 
135523240 13221780 849499334 