시간 제한메모리 제한제출정답맞힌 사람정답 비율
25 초 1024 MB2000.000%

문제

You are given a binary string $s$ of length $n$. Compute the sum of pairwise Hamming distances between all subsequences of string $s$ with length exactly $k$ for all $k$ from $1$ to $n$. Since the answers can be very large, find them modulo $40\,961$.

Hamming distance between two strings of equal length is the number of positions in which these two strings are different.

입력

The only line of input contains a string $s$ of length $n$ ($1 \le n \le 8 \cdot 10^{3}$) containing only characters "0" and "1".

출력

Print $n$ numbers: $k$-th of them must be the sum of pairwise Hamming distances between all subsequences of string $s$ with length exactly $k$, taken modulo $40\,961$.

예제 입력 1

11000110111001

예제 출력 1

48 4056 15326 31033 20654 29362 32472 13700 21357 12217 20411 12456 212 0

예제 입력 2

000

예제 출력 2

0 0 0