마법 상자

Rikka는 최근 마법 상자를 얻었다. 상자에는 한 줄로 늘어선 $n$개의 칸이 있고, 각 칸에는 영어 소문자가 하나씩 적혀 있다. 마법사인 Rikka는 칸에 주문을 걸어 마법의 힘을 줄 수 있다.

먼저 연속된 구간을 하나 골라, 그 구간의 문자를 이어 붙여 주문을 만든다. 이 주문으로 칸들에 "빛의 힘"을 준다. 예를 들어 왼쪽부터 'a', 'b', 'c'가 적힌 구간을 고르면 주문은 "abc"이다.

다음으로 연속된 구간을 하나 더 고른다. 앞서 고른 구간과 같아도 되고 달라도 된다. 같은 방식으로 주문을 만들어 칸들에 "어둠의 힘"을 준다.

마지막으로 두 힘을 동시에 받은 칸은 활성화된다.

Rikka는 두 주문이 완전히 같기를 원한다. $0$부터 $n$까지의 각 $k$에 대해, 같은 주문을 두 번 사용하여 정확히 $k$개의 칸을 활성화하는 방법의 수를 구하라.

첫째 줄에 영어 소문자로 이루어진 문자열 $s$가 주어진다. $i$번째 문자는 왼쪽에서 $i$번째 칸에 적힌 문자이다. $s$의 길이는 $1$ 이상 $5 \cdot 10^5$ 이하이다.

$n+1$개의 정수를 한 줄에 출력한다. $i$번째 정수는 정확히 $i-1$개의 칸을 활성화하는 방법의 수이다. 여기서 $n$은 입력 문자열의 길이이다.