This is the version of Ultra-Fast Solo Karuta small with larger constraints.
There is no particular restriction on submitting a solution meant 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.

• Reading card $x$ has a string $S_x$ written on it. $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 starts being read aloud, the player infers the reading card $x$ currently being read, finds the corresponding grabbing card $f(x)$ on the field, and takes it.
4. If there are still unread reading cards, 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, this requires intense concentration, so fatigue equal to the length of the string read aloud before taking the card is accumulated. That is, if the reading card is uniquely determined at the point when up to 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, the empty character is considered to have been read aloud as the $i$-th character, and a fatigue of $i$ is accumulated. Also, even if only $1$ card remains, the card cannot be taken until the $1$st character has been read aloud.

Compute 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 2000$
$1 \leq |S_i|$
$\sum |S_i| \leq 2 \times 10^5$
$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