超高速一人かるた smallの制約大きい版です。
small に large 用の解法を提出することは特に制限しませんが、 large をコンテスト中に解くつもりのある方は、他の方の提出を覗かないようお願いします。

問題文

かるた取りとは $N$ 枚の読み札と $N$ 枚の取り札を使ったゲームです。

• 読み札 $x$ には文字列 $S_x$ が書かれています。 $S_x \neq S_y (x \neq y)$
• 読み札 $x$ には対応する取り札 $f(x)$ が一つだけ存在します。
  異なる読み札が同じ取り札に対応することはありません（つまり一対一対応）。 $f(x) \neq f(y) (x \neq y)$

ゲームは次のように進行します。

1. 読手は $N$ 枚の読み札を持ち、競技者は $N$ 枚の取り札を場に並べます
2. 読手はまだ読んでいない読み札 $1$ 枚を等確率で選び、書かれている文字列を読み上げます。
3. 文字列が読み上げられ始めたら、競技者は今読まれている読み札 $x$ を推定し、 場から対応する取り札 $f(x)$ を探して取ります
4. 読まれていない読み札がまだ残っているなら 2. へ戻ります。 そうでないならゲームは終了です

太郎くんはかるたが得意なので、読み上げられている読み札が一意に定まった瞬間に取り札を取ることができます。 一意に定まらないうちに札を取ることはありません。
しかし大変集中力を要するため、取るまでに読み上げられた文字列長分の疲労度が蓄積されます。 つまり、 $i$ 文字目まで読み上げられた時点で読み札が一意に定まるとき、 $i$ の疲労度が蓄積されます。 ただし、 $i$ 文字目が読み上げられないことで一意に定まるとき、 $i$ 文字目に空文字が読み上げられたとみなして $i$ の疲労度が蓄積されます。 また、残る札が$1$枚であっても、$1$文字目が読み上げられてからでないと札を取ることはできません。

$N$ 枚の読み札の中から $K$ 枚読み上げられたときに蓄積される疲労度の期待値 $E_K$ を計算してください。
ただし、読み上げられ方のパターン数 ${}_N \mathrm{P} _K$ を掛けると丁度整数になるので、 $E_K \times {}_N \mathrm{P} _K \mod 1,000,000,007$ を出力してください。

入力

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

1行目に読み札・取り札の枚数 $N$ 、 続く $N$ 行に読み札 $i$ に書いてある文字列 $S_i$ が与えられます。

制約
$1 \leq N \leq 2000$
$1 \leq |S_i|$
$\sum |S_i| \leq 2 \times 10^5$
$S_i$ は小文字の英アルファベット'a'-'z'のみで構成される

出力

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

$K$ 行目に $E_K \times {}_N \mathrm{P} _K \mod 1,000,000,007$ を出力してください。

サンプル

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