409379: GYM103495 E Stone Ocean

In JoJo's world, some people are capable of transforming their inner spiritual power into a Stand. Cujoh Jolyne, like his father, has Stand Power. Her Stand is called Stone Free which can manipulate strings. Unfortunately, she was framed and sentenced to 15 years in the Green Dolphin Prison. She needs to use her Stand Power to help her regain her freedom from the Stone Ocean.

Since she has just acquired her Stand Power, it will take her some time to get used to it. Now there are $$$n$$$ strings $$$S_1,S_2,\dots S_n$$$. She wants to train her power with these strings by the following steps:

1. Set index $$$i=1$$$, and $$$T$$$ as an empty string.
2. Choose a character from $$$S_i$$$ uniformly and randomly, which means the probability of each character being selected is $$$\frac{1}{|S_i|}$$$, where $$$|S_i|$$$ is the length of $$$S_i$$$.
3. Append the chosen character to the back of $$$T$$$.
4. If $$$i<n$$$, increase $$$i$$$ by $$$1$$$ and go back to step 2.

After these steps, Cujoh Jolyne gets another string $$$T$$$. She defines the power value of $$$T$$$ as the number of pemutations $$$p_1,p_2,\dots,p_n$$$ that satisfy the following condition: $$$T_{p_1}T_{p_2}... . T_{p_n}$$$ is a palindrome.

Recall that a palindrome is defined as a string that is identical when read from left to right or right to left. For example, aa,aba,acca are palindromes while ab,cab are not. A permutation $$$p_1,p_2,\dots,p_n$$$ is a sequence where every integer from $$$1$$$ to $$$n$$$ appears exactly once.

To estimate the strength of her power, Cujoh Jolyne wants to know the expectation of the power value of string $$$T$$$.

The first line contains an integer $$$n$$$ ($$$2\le n\le 30$$$).

For the next $$$n$$$ lines, the $$$i$$$-th line contains a string $$$S_i$$$ ($$$1\leq |S_i| \leq 50000$$$, where $$$|S_i|$$$ is the length of $$$S_i$$$) consisting of lowercase letters only.

Output an integer indicating the expectation of the power value of string $$$T$$$ modulo $$$998244353$$$. Formally, let $$$M=998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\neq 0$$$. Output $$$p \cdot q^{-1}\bmod M$$$, where $$$q^{-1}$$$ denotes the multiplicative inverse of $$$q$$$ modulo $$$M$$$.

2
ab
ac

499122177

4
aabcc
abab
bbaa
acac

399297744

For the first example, string $$$T$$$ can be aa, ac, ba, bc with the same probability, and the power values of them are $$$2,0,0,0$$$ respectively. So the expectation of the power value is $$$\frac{2+0+0+0}{4}=\frac{1}{2}$$$.