A string ~S~ of length ~N~ is given. Alice has written all ~\binom{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 2\,000~

Subtask 4 [50%]

~1 \le N \le 200\,000~

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

---