This is the version with smaller constraints of Ultra-Fast Solo Karuta large.
There is no particular restriction on submitting a solution intended for large to small, but if you intend to solve large during the contest, please refrain from looking at other people's submissions.

Problem Statement

Karuta is a game played with $N$ reading cards and $N$ grabbing cards.

• The string $S_x$ is written on reading card $x$. $S_x \neq S_y (x \neq y)$
• For each reading card $x$, there exists exactly one corresponding grabbing card $f(x)$.
  Different reading cards never correspond to the same grabbing card (that is, the correspondence is one-to-one). $f(x) \neq f(y) (x \neq y)$

The game proceeds as follows.

1. The reader holds the $N$ reading cards, and the player lays out the $N$ grabbing cards on the field
2. The reader chooses $1$ reading card uniformly at random from those not yet read, and reads aloud the string written on it.
3. Once the string begins to be read aloud, the player deduces the reading card $x$ currently being read, then finds and takes the corresponding grabbing card $f(x)$ from the field
4. If there are still reading cards that have not been read, return to 2. Otherwise, the game ends

Taro is good at karuta, so he can take the grabbing card at the very moment the reading card being read is uniquely determined. He never takes a card before it is uniquely determined.
However, since this demands intense concentration, he accumulates fatigue equal to the length of the string read aloud before taking the card. That is, if the reading card is uniquely determined once the $i$-th character has been read aloud, a fatigue of $i$ is accumulated. However, if it is uniquely determined by the $i$-th character not being read aloud, an empty character is regarded as having been read aloud as the $i$-th character, and a fatigue of $i$ is accumulated. Also, even if only $1$ card remains, he cannot take the card until the $1$st character has been read aloud.

Calculate the expected value $E_K$ of the fatigue accumulated when $K$ cards out of the $N$ reading cards are read aloud.
Since multiplying it by the number of possible reading patterns ${}_N \mathrm{P} _K$ gives exactly an integer, output $E_K \times {}_N \mathrm{P} _K \mod 1,000,000,007$.

Input

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

The first line contains the number $N$ of reading cards and grabbing cards, and the following $N$ lines contain the string $S_i$ written on reading card $i$.

Constraints
$1 \leq N \leq 20$
$1 \leq |S_i|$
$\sum |S_i| \leq 10^3$
$S_i$ consists only of lowercase English letters 'a'-'z'

Output

$E_1 \times {}_N \mathrm{P} _1$
$E_2 \times {}_N \mathrm{P} _2$
$\vdots$
$E_N \times {}_N \mathrm{P} _N$

On the $K$-th line, output $E_K \times {}_N \mathrm{P} _K \mod 1,000,000,007$.

Sample

3
umr
uma
tsf

7
24
30

2
a
aa

4
6

12
a
b
c
d
e
f
g
h
i
j
k
l

12
264
3960
47520
475200
3991680
27941760
159667200
718502400
395007986
269017565
748019165