DA.DA.S

You are given $N$ strings $S_1,S_2,\ldots,S_N$, each consisting only of uppercase English letters.

Consider choosing some substrings of a string $X$ consisting only of uppercase English letters. Each chosen substring must equal one of $S_1,S_2,\ldots,S_N$, and no two chosen substrings may share a character position. A substring consists of consecutive characters. Chosen substrings may be adjacent.

You may choose multiple occurrences of the same string. Even if a string appears more than once among the given strings, the same occurrence in $X$ cannot be chosen multiple times.

Let $f(X)$ be the maximum number of substrings that can be chosen in this way. If no substring can be chosen, let $f(X)=0$. For example, if the only given string is $\texttt{AA}$, then $f(\texttt{AAAA})=2$: choose the first two characters and the last two characters. However, the two occurrences of in share the middle character, so .

Find the sum of $f(X)$ over all strings $X$ of length $M$ consisting only of uppercase English letters, modulo $998\ 244\ 353$.

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, output the sum of $f(X)$ over all uppercase English strings $X$ of length $M$, modulo $998\ 244\ 353$, on a separate line. Output the answers in the order the test cases appear in the input.

• $1\leq T\leq 100$.
• $1\leq N\leq 100$.
• $1\leq M\leq 10^{18}$.