A string $S$ of length $N$ is given. Alice has written all ${(\genfrac{}{}{0ex}{}{N+1}{2})}^2$ ordered pairs $(s,t)$ of substrings of $S$. For each pair, she computes the length of the longest common prefix of the two substrings. How many times does she write down each number from $1$ to $N$? As these numbers may be large, please output them modulo ${10}^9+7$.

Constraints

$S$ contains only lowercase English letters.

Subtask 1 [10%]

$1\le N\le 100$

Subtask 2 [20%]

$1\le N\le 500$

Subtask 3 [20%]

$1\le N\le 2000$

Subtask 4 [50%]

$1\le N\le 200000$

Input Specification

The first line contains a single integer $N$.
The next line contains the string $S$.

Output Specification

Output $N+1$ lines. On the $i^{\text{th}}$ line, print the number of pairs of substrings which have a longest common prefix of length $i-1$, modulo ${10}^9+7$.

Sample Input 1

3
ccc

Sample Output 1

0
27
8
1

Sample Input 2

4
dmpg

Sample Output 2

70
16
9
4
1